本题本质是求到起点星球的最短路范围在yi以内的星球个数之和

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,m,Q,a,b,x,y;
int h[N],e[N*10],ne[N*10],idx;//最多5000条双向边 也就是占用10000个存储位置
int dist[N][N],res,q[N];
//dist[i][j]记录从起点星球i到星球j的最短路径长度(因为权值是1 可以用bfs)
//由最短路模型可知 权值是1的情况下 节点第一次被遍历的时候就是最短路长度
void add(int a,int b) {ne[idx]=h[a],e[idx]=b,h[a]=idx++;}

void bfs(int start)
{
    int hh=0,tt=-1;
    q[++tt]=start,dist[start][start]=0;
    while(hh<=tt){
        int u=q[hh++];
        for(int i=h[u];i!=-1;i=ne[i])
            if(dist[start][e[i]]==0x3f3f3f3f) q[++tt]=e[i],dist[start][e[i]]=dist[start][u]+1;
    }
}

int main(){
    memset(h,-1,sizeof h),memset(dist,0x3f,sizeof dist);
    cin>>n>>m>>Q;
    for(int i=1;i<=m;i++) {cin>>a>>b;add(a,b),add(b,a);}
    //O(1e6)
    for(int i=1;i<=n;i++) bfs(i);
    //O(Q*n)
    for(int i=1;i<=Q;i++){
        cin>>x>>y;
        for(int i=1;i<=n;i++) if(dist[x][i]<=y) res++;
    }
    printf("%.2f",res*1.0/Q);
    return 0;
}