C++ 代码

#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
int mm[1010];  //mm数组用于记录从i星球出发可以到达最远的星球的距离；
bool st[1010];

struct ts{
    int cnt=0;
    int pos[1010];
}cop[1010];        //结构体数组存第i个星球能到那个星球与能到的星球的总个数；

int main()
{
    map<pii,int> mp;        //map中维护的信息是：从第i个星球出发,走k步所到达的不同的星球的总数；
    int n,m,Q;
    cin>>n>>m>>Q;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        cop[x].pos[cop[x].cnt]=y;
        cop[y].pos[cop[y].cnt]=x;
        cop[x].cnt++;
        cop[y].cnt++;
    }                       //读入每一条边；
    for(int i=1;i<=n;i++)  //bfs预处理，因为查询数量给的很大，所以需要预处理；
    {
        queue<int> q;
        memset(st,0,sizeof st);
        q.push(i);
        st[i]=true;
        int bk=i;    //bk用于维护q队列里与i星球距离为dis的最末尾星球编号；
        int res=1;  //res用于维护经过的不同星球的总数；
        int dis=1;  //与i星球的距离；
        mp[{i,0}]=1;    //初始化；
        while(q.size())     //bfs
        {
            int t=q.front();
            q.pop();
            for(int j=0;j<cop[t].cnt;j++)
            {
                if(!st[cop[t].pos[j]])
                {
                    q.push(cop[t].pos[j]);
                    st[cop[t].pos[j]]=true;
                    res++;
                }
            }
            if(t==bk)       //如果上一个出队的元素与bk一致，更新mp，更新bk，更新dis；
            {
                mp[{i,dis}]=res;
                mm[i]=dis;
                dis++;
                bk=q.back();
            }
        }
    }
    int query=Q;
    int ans=0;
    while(query--)      //读入查询；
    {
        int x,y;
        cin>>x>>y;
        if(y>mm[x])ans+=mp[{x,mm[x]}]; //防止越界；
        else ans+=mp[{x,y}];
    }
    printf("%.2lf",(double)ans/(double)Q);

    return 0;
}