http://poj.org/problem?id=1125、
题意：在经纪人的圈子里，他们各自都有自己的消息来源，并且也只相信自己的消息来源，他们之间的信息传输也需要一定的时间。现在有一个消息需要传播，求从哪个经纪人开始传播所需的时间是最短的，所有经纪人都要收到信息，输出时间和那个经纪人的编号。
思路：用floyd算出两个点之间的短的传播时间。当这个点传播到某个点的时间最大时，要么是传播不到，要么这个点就是最后一个经纪人所需要接受到信息的最短时间
#include <stdio.h>
#include <string.h>
#define inf 999999 int graph[ ][ ],n; void floyd()
{
int k,i,j,Min,loc,Minroad;
for( k = ; k <= n ; k++ ) //这五行代码就是floyd的思想，从某个点到某个点的最短路径有可能是他们直接相连的，也有可能是通过其他的点相连接的。
for( i = ; i <= n ; i++ )
for( j = ; j <= n ; j++ )
if( i != j && graph[ i ][ j ] > graph[ i ][ k ] + graph[ k ][ j ] )
graph[ i ][ j ] = graph[ i ][ k ] + graph[ k ][ j ];
Min = inf;
for( i = ; i <= n ; i++ ) //枚举每个经纪人。
{
Minroad = ;
for( j = ; j <= n ; j++)
if( i != j && Minroad < graph[ i ][ j ] ) //求出他们的所需的最长时间
Minroad = graph[ i ][ j ];
if( Min > Minroad )
{
Min = Minroad;
loc = i;
}
}
printf("%d %d\n",loc,Min);
} int main()
{
// freopen("in.txt","r",stdin);
int x,a,b;
while(scanf("%d",&n),n)
{
for(int i = ; i <= n ; i++)
for(int j = ; j <= n ; j++)
{
graph[ i ][ j ] = inf;
}
for(int i = ; i <= n ; i++)
{
scanf("%d",&x);
for(int j = ; j < x ; j++)
{
scanf("%d%d",&a,&b);
graph[ i ][ a ] = b;
}
}
floyd();
}
return ;
}