Description
Input
Output
Sample Input
3 2 2 4 3 5 2 1 2 3 6 2 1 2 2 2 5 3 4 4 2 8 5 3 1 5 8 4 1 6 4 10 2 7 5 2 0 2 2 5 1 5 0
Sample Output
3 2 3 10
Source
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f,MAX = 300; int d[MAX],map[MAX][MAX]; int main() { int y,t,T,n; while(~scanf("%d",&T)&&T){ memset(d,0,sizeof(d)); for(int i = 1; i <=T;i++) for(int j = 1; j <= T;j++) map[i][j] = inf; int i; for( i = 1; i <= T; i++){ scanf("%d",&n); while(n--){ scanf("%d%d",&y,&t); map[i][y] = t; } } for(int k = 1; k <= T; k++){ for(int i = 1; i <=T; i++){ for(int j = 1; j <= T ;j++){ if(i!=k&&i!=j&&k!=j) map[i][j] = min(map[i][j],map[i][k]+map[k][j]); } } }//每一种都要满足 int min1 = inf, k; for(int i = 1; i <= T ; i++){ for(int j = 1; j <= T; j++) if(map[i][j] > d[i]&&i!=j) d[i] = map[i][j]; if(d[i] < min1){ min1 = d[i]; k = i; } } if(min1 == inf) printf("disjoint\n"); else printf("%d %d\n",k,min1); } return 0; }
原文:http://www.cnblogs.com/zero-begin/p/4321382.html