题目描述

就强调一点，先看样例，他并不是求”一次性”能到多少不同的星球，

而是只要这个星球能在y次传送内到达，

就会被纳入计算(本蒟蒻一开始没注意，还想了好久第一个为什么是3,qwq)

样例

输入样例：
3 2 3
1 2
2 3
2 1
2 0
1 1

输出样例：
2.00

样例解释
第一个盲盒可以旅行到 1,2,3。
第二个盲盒可以旅行到 2。
第三个盲盒可以旅行到 1,2。
所以期望是 (3+1+2)/3=2.00

思路：

不难想可以以每个点为起点,跑一遍BFS，只要这个点在y次传送门内可达，那就纳入

最后计算期望。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010 , M = 10010;

int d[N][N];   //表示以i为起点，到点j的距离
int n,m,Q,ans;
int h[N], e[M], ne[M], idx;
bool st[N];
int q[N];

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

void bfs(int s){       //以s为起点BFS，模板题
    memset(st, 0, sizeof st);
    memset(q,0,sizeof q);
    int hh=0,tt=-1;
    d[s][s]=0;
    q[++tt]=s;
    st[s]=true;
    while (hh<=tt){
        int t = q[hh++];
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if (st[j])  continue;

            st[j]=true;
            d[s][j]=d[s][t]+1;
            q[++tt]=j;
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&Q);
    memset(h, -1, sizeof h);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    for(int i=1;i<=n;i++){    //记得初始化成无穷大
        for(int j=1;j<=n;j++){
            d[i][j]=0x3f3f3f3f;
        }
    }
    for(int i=1;i<=n;i++)  bfs(i);  //以每个点为起点BFS
    for(int i=1;i<=Q;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        for(int i=1;i<=n;i++){
            if (d[x][i]<=y)  ans++;  //只要小于等于y就可以纳入
        }
    }
    printf("%.2f",ans * 1.0 / Q);
    return 0;
}