星际旅行 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 1000 + 100;
int n, m, q, u, v, x, y;
double ans;
bool vis[maxn];
int dis[maxn];
int cnt[maxn][maxn];
vector<int> G[maxn];
queue<int> que;

void bfs(int s) {
    memset(vis, 0, sizeof(vis));
    que.push(s);
    dis[s] = 0;
    vis[s] = true;

    while (!que.empty()) {
        int tmp = que.front();
        que.pop();
        for (int i = 0; i < G[tmp].size(); ++i) {
            int pos = G[tmp][i];
            if (!vis[pos]) {
                vis[pos] = true;
                dis[pos] = dis[tmp] + 1;
                que.push(pos);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            continue;
        }
        ++cnt[s][dis[i]];
    }
    for (int i = 1; i <= n; ++i) {
        cnt[s][i] += cnt[s][i - 1];
    }
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n >> m >> q;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        bfs(i);
    }
    for (int i = 0; i < q; ++i) {
        cin >> x >> y;
        ans += cnt[x][y];
    }
    printf("%.2lf\n", ans / q);

    return 0;
}