poj 1125 (floyd)

题意：在经纪人的圈子里，他们各自都有自己的消息来源，并且也只相信自己的消息来源，他们之间的信息传输也需要一定的时间。现在有一个消息需要传播，求从哪个经纪人开始传播所需的时间是最短的，所有经纪人都要收到信息，输出时间和那个经纪人的编号。

思路：用floyd算出两个点之间的短的传播时间。当这个点传播到某个点的时间最大时，要么是传播不到，要么这个点就是最后一个经纪人所需要接受到信息的最短时间

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define inf 999999
 4 
 5 int graph[ 105 ][ 105 ],n;
 6 
 7 
 8 void floyd()
 9 {
10     int k,i,j,Min,loc,Minroad;
11     for( k = 1 ; k <= n ; k++ )        //这五行代码就是floyd的思想，从某个点到某个点的最短路径有可能是他们直接相连的，也有可能是通过其他的点相连接的。
12         for( i = 1 ; i <= n ; i++ )
13             for( j = 1 ; j <= n ; j++ )
14                 if( i != j && graph[ i ][ j ] > graph[ i ][ k ] + graph[ k ][ j ] )    
15                     graph[ i ][ j ] = graph[ i ][ k ] + graph[ k ][ j ];
16         Min = inf;
17     for( i = 1 ; i <= n ; i++ )         //枚举每个经纪人。
18     {
19         Minroad = 0;
20         for( j = 1 ; j <= n ; j++)
21             if( i != j && Minroad < graph[ i ][ j ] )    //求出他们的所需的最长时间
22                 Minroad = graph[ i ][ j ];
23         if( Min > Minroad )
24         {
25             Min = Minroad;
26             loc = i;
27         }
28     }
29     printf("%d %d
",loc,Min);
30 }
31 
32 
33 int main()
34 {
35  //   freopen("in.txt","r",stdin);
36     int x,a,b;
37     while(scanf("%d",&n),n)
38     {
39         for(int i = 0 ; i <= n ; i++)
40             for(int j = 0 ; j <= n ; j++)
41             {
42                  graph[ i ][ j ] = inf;
43             }
44         for(int i = 1 ; i <= n ; i++)
45         {
46             scanf("%d",&x);
47             for(int j =0  ; j < x ; j++)
48             {
49                 scanf("%d%d",&a,&b);
50                 graph[ i ][ a ] = b;
51             }
52         }
53         floyd();
54     }
55     return 0;
56 }