首页 > 代码库 > Zoj 2913 Bus Pass BFS

Zoj 2913 Bus Pass BFS

2024-07-11 12:06:51   229人阅读

题意： 给你一张图，和一些指定的点，找一个点使得这些指定的点到这个点的距离的最大值最小

对每一个指定的点都做一遍BFS，更新到达每个点的距离，取较大值，然后扫一遍所有的点，找出最小即可。

注意：不同于走格子，因为方向比较多，所以要在扩展节点的时候就更新vis数组，不然有可能导致某个点的距离因为重复更新而不是最小值。

并且不要漏了一开始就更新起点的vis

 

#include <cstdio>#include <vector>#include <cstring>#include <algorithm>#include <map>#include <queue>using namespace std;const int maxn = 10000 + 5;vector<int> edge[maxn];bool vis[maxn];int maxv[maxn];void bfs(int u) {    queue<int> q; q.push(u);    queue<int> dq; dq.push(1);    memset(vis,0,sizeof(vis));    vis[u] = true;    while(!q.empty()) {        int dis = dq.front(); dq.pop();        u = q.front(); q.pop();        maxv[u] = max(maxv[u],dis);        int m = edge[u].size();        for(int i = 0;i < m;i++) {            if(!vis[edge[u][i]]) {                q.push(edge[u][i]);                dq.push(dis + 1);                vis[edge[u][i]] = true;            }        }    }}int main() {    int T; scanf("%d",&T);    for(int kase = 1;kase <= T;kase++) {        int nz,nr; scanf("%d%d",&nz,&nr);        memset(maxv,0,sizeof(maxv));        for(int i = 0;i < maxn;i++) edge[i].clear();        for(int i = 0;i < nz;i++) {            int mz,mr; scanf("%d%d",&mz,&mr);            for(int j = 0;j < mr;j++) {                int tmp; scanf("%d",&tmp);                edge[mz].push_back(tmp);                edge[tmp].push_back(mz);            }        }        for(int i = 0;i < nr;i++) {            int mr; scanf("%d",&mr);            for(int j = 0;j < mr;j++) {                int tmp; scanf("%d",&tmp);                bfs(tmp);            }        }        int ans = 20000000,ansi = ans;        for(int i = 0;i < maxn;i++) if(edge[i].size()) {            if(maxv[i] < ans) {                ans = maxv[i]; ansi = i;            }        }        printf("%d %d\n",ans,ansi);    }    return 0;}

　　


联系
我们