java 代码

import java.util.*;

public class Main{
    public static int N = 1010;
    public static int M = 10010;
    public static int n , m , Q , idx ;
    public static int ans;
    public static int[] h = new int[N];
    public static int[] e = new int[M];
    public static int[] ne = new int[M];
    public static boolean st[];
    public static int dist[][] = new int[N][N];
    public static int q[] = new int[N];
    public static int max = 0x3f3f3f3f;

    public static void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx;
        idx ++;
    }

    public static void bfs(int u){
        st = new boolean[N];
        int hh = 0;
        int tt = -1;
        dist[u][u] = 0;
        q[++tt] = u;
        st[u] = true;

        while(hh <= tt){
            int t = q[hh++];
            for(int i = h[t];i != -1;i = ne[i]){
                int j = e[i];

                if(st[j] == true) continue;
                st[j] = true;

                dist[u][j] = dist[u][t] + 1;
                q[++tt] = j;
            }
        }

    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Q = sc.nextInt();
        Arrays.fill(h,-1);

        while(m-- > 0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            add(a,b);
            add(b,a);
        }

        for(int i = 1;i <= n;i ++) Arrays.fill(dist[i],max);

        for(int i = 1;i <= n;i ++) bfs(i);

        for(int i = 1;i <= Q;i ++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            for(int j = 1;j <= n;j ++)
                if(dist[x][j] <= y) ans ++;
        }

        System.out.printf("%.2f",ans*1.0/Q);
    }
}