本文共 1677 字，大约阅读时间需要 5 分钟。
题目链接：
大意是有一张无向不带权的图，两个人同时从s点出发，分别前往a点和b点，且每个人应该走s到a和s到b的最短路，问他们可以一起走的最大距离是多少。
我一开始的想法是以s为源点bfs，做出所有点的前驱，然后判断a回到s和b回到s有多少点是共享的。WA了，后来一想，这么做确实是错的，因为很有可能a回到s的路是一条b不会走的路。然后变了下思路，直接分别以s，a和b为源点bfs，做出三个dis数组，枚举图中所有点，判断是否在s到a以及s到b的最短路上，如果是的话，则更新答案。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std;14 15 16 const int N=323456;17 18 struct Edge {19 int to,next;20 Edge() {}21 Edge(int _to,int _next):to(_to),next(_next) {}22 } edge[N<<2];23 int idx=1,head[N];24 inline void addedge(int u,int v) {25 edge[++idx]=Edge(v,head[u]);26 head[u]=idx;27 }28 bool vis[N];29 30 void bfs(int s,int *dis) {31 memset(vis,false,sizeof vis);32 queue que;33 que.push(s);34 vis[s]=true;35 dis[s]=0;36 while (!que.empty()) {37 int u=que.front();38 que.pop();39 for (int k=head[u];k;k=edge[k].next) {40 int v=edge[k].to;41 if (vis[v]) continue;42 dis[v]=dis[u]+1;43 vis[v]=true;44 que.push(v);45 }46 }47 }48 int dis[3][N];49 int main () {50 int n,m;51 while (scanf("%d %d",&n,&m)==2) {52 int s,a,b;53 scanf("%d %d %d",&s,&a,&b);54 idx=1;memset(head,0,sizeof head);55 for (int i=1;i<=m;i++) {56 int u,v;57 scanf("%d %d",&u,&v);58 addedge(u,v);59 addedge(v,u);60 }61 bfs(s,dis[0]);62 bfs(a,dis[1]);63 bfs(b,dis[2]);64 int da=dis[0][a];65 int db=dis[0][b];66 int ret=0;67 for (int i=1;i<=n;i++) {68 if (dis[0][i]+dis[1][i]==da&&dis[0][i]+dis[2][i]==db) {69 ret=max(ret,dis[0][i]);70 }71 }72 cout< <
转载于:https://www.cnblogs.com/micrari/p/5478169.html
