寻找从 i 到 X, 再从 X 到 i 的最短路
可以在正向图中从 X 开始跑一遍最短路, 每个点的距离 dis1[i] 当作从 X 回到点 i 的距离
再将图反向从 X 再跑一遍, 每个点的距离 dis2[i] 当作从 i 到点 X 的距离
最后搜索 dis1[i]+dis2[i] 值最大的输
- /*
- Written By StelaYuri
- */
- #include<bits/stdc++.h>
- #define INF 0x3f3f3f3f
- using namespace std;
- typedef pair<short,int> P;
- vector<P> graph1[1005],graph2[1005];
- int N,M,X,dis1[1005],dis2[1005];
- bool vis1[1005],vis2[1005];
- queue<short> q;
- int main()
- {
- iOS::sync_with_stdio(0);cin.tie(0);
- int i,j,d,cnt,len,ans=0;
- short a,b,id;
- cin>>N>>M>>X;
- for(i=0;i<M;i++)
- {
- cin>>a>>b>>d;
- graph1[a].push_back(P(b,d));
- graph2[b].push_back(P(a,d));
- }
- memset(dis1,INF,sizeof dis1);
- memset(dis2,INF,sizeof dis2);
- memset(vis1,false,sizeof vis1);
- memset(vis2,false,sizeof vis2);
- dis1[X]=dis2[X]=0;
- vis1[X]=vis2[X]=true;
- q.push(X);
- while(!q.empty())
- {
- id=q.front();
- q.pop();
- cnt=graph1[id].size();
- for(i=0;i<cnt;i++)
- {
- len=dis1[id]+graph1[id][i].second;
- if(!vis1[graph1[id][i].first]||len<dis1[graph1[id][i].first])
- {
- dis1[graph1[id][i].first]=len;
- vis1[graph1[id][i].first]=true;
- q.push(graph1[id][i].first);
- }
- }
- }
- q.push(X);
- while(!q.empty())
- {
- id=q.front();
- q.pop();
- cnt=graph2[id].size();
- for(i=0;i<cnt;i++)
- {
- len=dis2[id]+graph2[id][i].second;
- if(!vis2[graph2[id][i].first]||len<dis2[graph2[id][i].first])
- {
- dis2[graph2[id][i].first]=len;
- vis2[graph2[id][i].first]=true;
- q.push(graph2[id][i].first);
- }
- }
- }
- for(i=1;i<=N;i++)
- {
- if(i==X)
- continue;
- ans=max(ans,dis1[i]+dis2[i]);
- }
- cout<<ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3395552.html