POJ 1125 Stockbroker Grapevine

最短路的题目。此题的题意是相当蛋疼啊。来看翻译下输入输出

输入
你的程序包含多组股票经纪人的输入数据。每组以股票经纪人的人数开始。接下来的几行是每个经纪人与其他人接触的一些信息，包括这些人都是谁，以及将讯息传达到他们所需的时间。每个经纪人与其他人接触信息的格式如下：开头的第一个数表示共有n个联系人，接下来就有n对整数。每对整数列出的第一个数字指的是一个联系人（例如，一个'1'是指编号1的人），其次是在传递一个信息给那个人时所采取分钟的时间。没有特殊的标点符号或空格规则。
每个人的编号为1至经纪人数目。所花费的传递时间是从1到10分钟（含10分种）。股票经纪的人数范围是从1到100。当输入股票经纪人的人数为0时，程序终止。
输出
在对于每一组数据，你的程序必须输出一行，包括的信息有传输速度最快的人，以及在最后一个人收到消息后，所总共使用的时间（整数分钟计算）。
你的程序可能会收到的一些关系会排除一些人，也就是有些人可能无法访问。如果你的程序检测到这样一个破碎的网络，只需输出消息“disjoint”。请注意，所花费的时间是从A传递消息到B，B传递信息到A不一定是花费同样的传递时间，但此类传播也是可能的。

其实看到这还是不明白的。其实让求的是最短路中距离最大的。就第一组数据。经过一边Floyd后。

是这样的。第一行的最大值 5，第二行的 6，第三行的 2 。。哪一行的最小？第三行所以输出3.然后输出的是行最大值的最小值。

Floyd

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 long map[310][310];
 5 int main()
 6 {
 7     int a,b,n,m,t,i,j,k;
 8     while(~scanf("%d",&t))
 9     {
10         int max=10000;
11         if(t==0)
12             break;
13         for(i=0;i<=t;i++)
14             for(j=0;j<=t;j++)
15                 map[i][j]=1000000;
16                 for(i=0;i<t;i++)
17                 map[i][i]=0;
18         for(i=1;i<=t;i++)
19         {
20             scanf("%d",&n);
21             for(j=1;j<=n;j++)
22             {
23                 scanf("%d%d",&a,&b);
24                 map[i][a]=b;
25             }
26         }
27         for(k=1;k<=t;k++)
28             for(i=1;i<=t;i++)
29                 for(j=1;j<=t;j++)
30                     if(map[i][j]>(map[i][k]+map[k][j]))
31                        map[i][j]=map[i][k]+map[k][j];
32         for(i=1;i<=t;i++)
33         {
34             int min=0;
35             for(j=1;j<=t;j++)
36             {
37                 if(i!=j&&map[i][j]>min)
38                     min=map[i][j];
39             }
40             if(min<max)
41             {
42                 max=min;
43                 m=i;
44             }
45         }
46         if(max<10000)
47             printf("%d %d\n",m,max);
48         else
49             puts("disjoint");
50     }
51     return 0;
52 }