题解：P11046 [蓝桥杯 2024 省 Java B] 星际旅行

虽然是 Java 题，但我还是用 C++ 做了。

题目传送门

题目大意

给出一张无向图，总共有 $Q$ 次询问，求所有与 $x_i$ 的距离不超过 $y_i$ 的结点的个数，输出每次询问的答案的平均数。

思路讲解

由于时限较大且数据较小，所以我们可以考虑直接 bfs 统计所有距离不超过 $y_i$ 的结点，将答案累加后再除 $Q$。

算法复杂度为 $O((n+m)\times Q)$。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int INF=(1LL<<31-1);
int n,m,q;
vector<int> g[1003];
int bfs(int x,int y){
    int sum=1,dist[1003];//要算上x，初始化为1
    queue<int> q;
    q.push(x);
    for(int i=1;i<=n;i++)
        dist[i]=INF;//初始化dist数组
    dist[x]=0;
    while(q.size()){
        int f=q.front(),len=g[f].size();
        q.pop();
        if(dist[f]==y)//如果为y，说明已经没有距离不超过y的未被访问的点
            break;//跳出循环
        for(int i=0;i<len;i++)
            if(dist[g[f][i]]==INF)
                sum++,dist[g[f][i]]=dist[f]+1,q.push(g[f][i]);
    }
    return sum;
}
int main(){
    int ans=0;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=1;i<=q;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        ans+=bfs(a,b);//累加答案
    }
    printf("%.2lf",1.0*ans/q);
    return 0;
}

原文地址：https://blog.csdn.net/andycode_/article/details/142529539

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！