题意：有分别来自 N 个农场的 N 头牛去农场 X 嗨皮，农场间由 M 条有向路径连接。每头牛来回都挑最短的路走，求它们中走的路的最大长度？
(1 ≤ X ≤ N).
(1 ≤ M ≤ 100,000)
floyd超时，dir遍历所有点N*N2超时
思路：来个反向图，全部以x为起点，两次dir即可。（正向图s起点x终点即反向图x起点s终点）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long LL; #define N 1000+8 int mp1[N][N],mp2[N][N],dist1[N],dist2[N],vis[N],n; void dir(int s,int mp[][N],int dist[]) { int i,j,k; for(i=1; i<=n; i++) { vis[i]=0; dist[i]=mp[s][i]; } vis[s]=1; for(j=1; j<n; j++) { int min1=1e9; for(i=1; i<=n; i++) { if(!vis[i]&&dist[i]<min1) { min1=dist[i]; k=i; } } vis[k]=1; for(i=1; i<=n; i++) { if(!vis[i]) dist[i]=min(dist[i],dist[k]+mp[k][i]); } } } int main() { int x,m,i,j,a,b,c; scanf("%d%d%d",&n,&m,&x); for(i=1; i<=n; i++) for(j=1; j<=n; j++) { if(i==j) mp1[i][j]=mp2[i][j]=0; else mp1[i][j]=mp2[i][j]=1e9; } while(m--) { scanf("%d%d%d",&a,&b,&c); mp1[a][b]=c; mp2[b][a]=c; } dir(x,mp1,dist1); dir(x,mp2,dist2); int max1=0; for(i=1; i<=n; i++) { if(i==x) continue; max1=max(max1,dist1[i]+dist2[i]); } printf("%d\n",max1); return 0; }
