题目描述
给出n个节点和m条有向边，求从每个节点到x往返的最短路径中的最大值。
思路
由于正着思考我们虽然只能一次求出x到其他各点，但每次要求出i到x的最短路，显然会T掉。我们考虑建原图的反图，那么i到x的最短路可以转化为再反图上x到i的最短路，因为边权不变，最短路径经过的节点是相同。进行两遍Dijkstra即可。
代码
#include <bits/stdc++.h> using namespace std; const int MAXM=100005,MAXN=1005; struct aa { int nxt,to,w; }e[MAXM][2]; int head[MAXN][2],tot[2],dis[MAXN][2],x; bool used[MAXN][2]; void add_edge(int x,int y,int v,int f) { e[++tot[f]][f].nxt=head[x][f]; head[x][f]=tot[f]; e[tot[f]][f].to=y; e[tot[f]][f].w=v; } void Dijkstra(int f) { priority_queue<pair<int,int> >q; dis[x][f]=0;q.push(make_pair(0,x)); while(!q.empty()) { int u=q.top().second;q.pop(); if(used[u][f])continue ; used[u][f]=1; for(int i=head[u][f];i;i=e[i][f].nxt) { int v=e[i][f].to; if(dis[v][f]>dis[u][f]+e[i][f].w) { dis[v][f]=dis[u][f]+e[i][f].w; q.push(make_pair(-dis[v][f],v)); } } } } int main() { memset(dis,0x3f,sizeof(dis)); int n,m; scanf("%d%d%d",&n,&m,&x); for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add_edge(a,b,c,0); add_edge(b,a,c,1); } Dijkstra(0);Dijkstra(1); int ans=0; for(int i=1;i<=n;i++) if(i!=x)ans=max(ans,dis[i][0]+dis[i][1]); printf("%d",ans); return 0; }