题目：
编号为1…N的N个农场中的每一个（1≤N≤1000）的一头奶牛将参加在#X农场（1≤X≤N）举行的大型奶牛聚会。总共M（1≤M≤100,000）单向（单向道路连接成对的农场;道路i需要Ti（1≤Ti≤100）单位时间来遍历。每头奶牛都必须走到聚会上，当聚会结束时，回到她的农场。每头奶牛都很懒，因此选择最短时间的最佳路线。由于道路是单向的，因此牛的返回路线可能与她原来的路线不同。
在所有的奶牛中，奶牛必须花费多长时间走到聚会和回来的时间是多长？
输入
第1行：三个以空格分隔的整数：N，M和X.
第2行… M + 1：第i + 1行描述具有三个以空格分隔的整数的道路i：Ai，Bi和Ti。描述的道路从农场Ai运行到农场Bi，需要Ti时间单位来遍历。
输出
第1行：一个整数：任何一头奶牛必须行走的最长时间。
Sample Input
4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3
Sample Output
10
样例解释：
奶牛4直接进入该聚会（3个单位），并通过1号和3号农场（7个单位）返回，总共10个时间单位。
解题思路：题上要求输入的路径是单向的，首先第一次用Dijkstra算法求出x点到其他点的最短距离，然后交换e[i][j]和e[j][i]中的值，这样从各点到x的最短距离就又可以看成x到各点的距离。注意：可能一个坐标连续存入两次，所以存入时判断较小的存入；还有就是用Floyd算法运行时由于连续三个for循环会时间超限。
程序代码：
#include<stdio.h> #include<string.h> int e[1005][1005],dis[1005],book[1005],a[1005]; int n,x; int inf=99999999; void get_dis() { int i,j,min,v,u; for(i=1;i<=n;i++) dis[i]=e[x][i]; for(i=1;i<=n;i++) book[i]=0; book[x]=1; for(i=1;i<n;i++) { min=inf; for(j=1;j<=n;j++) { if(book[j]==0&&dis[j]<min) { min=dis[j]; u=j; } } book[u]=1; for(v=1;v<=n;v++) { if(e[i][j]<inf) { if(book[v]==0&&dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v]; } } } } int main() { int i,j,m,t1,t2,t3,min,k,max,t; while(scanf("%d%d%d",&n,&m,&x)!=EOF) { max=-1; memset(dis,0,sizeof(dis)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0; else e[i][j]=inf; for(i=1;i<=m;i++) { scanf("%d%d%d",&t1,&t2,&t3); if(t3<e[t1][t2]) e[t1][t2]=t3; } get_dis(); for(i=1;i<=n;i++) a[i]=dis[i]; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) { t=e[i][j]; e[i][j]=e[j][i]; e[j][i]=t; } get_dis(); for(i=1;i<=n;i++) { if(max<dis[i]+a[i]) { max=dis[i]+a[i]; } } printf("%d\n",max); } return 0; }
