poj 1125Stockbroker Grapevine（最短路）

题意很难懂一个人可以同时向多个人传递信息找出每个人向所有人传递完信息后的最大值再找出这些最大值中的最小值就是结果

View Code

 1 #include <iostream>
 2 #include<string.h>
 3 #include<cstdio>
 4 #define INF 0x3f3f3f
 5 using namespace std;
 6 int w[101][101];
 7 int main()
 8 {
 9     int i,j,k,n,m,t,v,w1,x;
10     while(scanf("%d",&t)&&t)
11     {
12         memset(w,INF,sizeof(w));
13         for(i = 1; i <= t; i++)
14         {
15             scanf("%d",&n);
16             while(n--)
17             {
18                 scanf("%d %d",&v,&w1);
19                 w[i][v] = w1;
20             }
21         }
22         for(i = 1 ; i <= t ; i++)
23         for(j = 1; j <= t ; j++)
24         for(k = 1 ; k <= t ; k++)
25         if(w[j][i]+w[i][k]<w[j][k])
26         w[j][k] = w[j][i]+w[i][k];
27         int min = INF,max;
28         for(i = 1 ; i <= t ; i++)
29         {
30             max = -1;
31             for(j = 1 ;j <= t ; j++)
32             if(i!=j&&max<w[i][j])
33             max = w[i][j];
34             if(min>max)
35             {
36                 min = max;
37                 x = i;
38             }
39         }
40         printf("%d %d\n",x,min);
41     }
42     return 0;
43 }