题意：有N个股票经济人可以互相传递消息，他们之间存在一些单向的通信路径。现在有一个消息要由某个人开始传递给其他所有人，问应该由哪一个人来传递，才能在最短时间内
让所有人都接收到消息。若不存在这样一个人，则输出disjoint
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 using namespace std; 7 #define inf 9999999 8 #define N 105 9 int n,map[N][N]; 10 11 void Floyd()//Floyd算每两个点之间的距离 12 { 13 for(int k=1; k<=n; k++) 14 { 15 for(int i=1; i<=n; i++) 16 { 17 if(k==i||map[i][k]==inf) continue; 18 for(int j=1; j<=n; j++) 19 { 20 if(j==k||map[k][j]==inf) continue; 21 map[i][j] = min(map[i][j],map[i][k]+map[k][j]); 22 } 23 } 24 } 25 } 26 27 int main() 28 { 29 while(scanf("%d",&n)&&n) 30 { 31 for(int i=1; i<=n; i++) 32 for(int j=1; j<=n; j++) 33 { 34 if(i==j) map[i][j] = 0; 35 else map[i][j] = inf; 36 } 37 int m,a,t; 38 for(int i=1; i<=n; i++) 39 { 40 scanf("%d",&m); 41 for(int j=1; j<=m; j++) 42 { 43 scanf("%d%d",&a,&t); 44 map[i][a] = t; 45 } 46 } 47 Floyd(); 48 int ans=inf,temp; 49 int num,flag,flag1=0;//flag1 记录是否存在某个点可以到其他任何点 50 for(int i=1; i<=n; i++) 51 { 52 flag = 1; temp = 0; 53 for(int j=1; j<=n; j++) 54 { 55 if(i==j) continue; 56 if(map[i][j]==inf) //如果从i到j没路。。说明不可以从i这个点出发 57 { 58 flag = 0; 59 continue; 60 } 61 temp = max(temp,map[i][j]);//记录从i开始到所有点之间最长的路 62 } 63 if(flag&&ans>temp) //如果i到所有点都有路并且最长的路比之前小 64 { 65 num = i; 66 ans = temp; 67 flag1 = 1; 68 } 69 } 70 if(flag1) 71 printf("%d %d ",num,ans); 72 else printf("disjoint "); 73 } 74 return 0; 75 }