题意：求有向图的往返最短路的最长长度。
分析：求第一次到所有点的距离可以用一次Dijkstra求最短路求出来。考虑回来的路，想想就知道，从每个点回来的路即为将边的方向反转再求一次最短路后的结果。
所以此题为求两次最短路。
代码：
#include#include #include #include #include #define Mod 1000000007using namespace std;#define N 1007int mp[N][N],n,m;int dis[N],vis[N],dis2[N];void Dijastra(int s,int *dis){ int now = s; int i,k; dis[now] = 0; vis[now] = 1; for(i=1;i<=n;i++) { for(k=1;k<=n;k++) //order 1 { if(mp[now][k] != Mod && dis[now] + mp[now][k] < dis[k]) dis[k] = dis[now] + mp[now][k]; } int mini = Mod; //order 2 for(k=1;k<=n;k++) { if(dis[k] < mini && !vis[k]) { now = k; mini = dis[k]; } } vis[now] = 1; }}int main(){ int u,v,w,i,j,x; while(scanf("%d%d%d",&n,&m,&x)!=EOF) { for(i=1;i<=n;i++) dis[i] = Mod; dis[x] = 0; for(i=1;i<=n;i++) { for(j=i;j<=n;j++) mp[i][j] = mp[j][i] = Mod; mp[i][i] = 0; } while(m--) { scanf("%d%d%d",&u,&v,&w); mp[u][v] = w; } memset(vis,0,sizeof(vis)); Dijastra(x,dis); for(i=1;i<=n;i++) dis2[i] = Mod; dis2[x] = 0; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { swap(mp[i][j],mp[j][i]); } } memset(vis,0,sizeof(vis)); Dijastra(x,dis2); int maxi = -1; for(i=1;i<=n;i++) { if(dis[i] < Mod && dis2[i] < Mod) maxi = max(maxi,dis[i]+dis2[i]); } printf("%d\n",maxi); } return 0;}