题意： n个人炒股，每一个人都能够给其它人报信，第 1 行 n，第x行 第一个 是 第 x-1个人能够给几个人报信，后面是能给哪些人报信和报信的时间 ，问从第几个人開始报信所用的时间最少
水题，Floyd 一遍 过；
ME 676KB
TI 16MS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <algorithm>
const int INF = 1e7;
const int N = 105;
using namespace std;
int mapp[N][N],n;
void init()
{
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=n;j++)
{
mapp[i][j] = INF;
}
}
}
void Floyd()
{
int k,j,i;
for(k = 1;k<=n;k++)
{
for(i = 1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(mapp[i][j] > mapp[i][k] + mapp[k][j])
mapp[i][j] = mapp[k][j] + mapp[i][k];
}
}
}
}
int main()
{
int s,wz,ti;
while(scanf("%d",&n),n)
{
init();
for(int i = 1;i<=n;i++)
{
scanf("%d",&s);
for(int j = 1;j<=s;j++)
{
scanf("%d%d",&wz,&ti);
mapp[i][wz] = ti;
}
}
Floyd();
int st = -1,maxx = 0,ti = INF;
for(int i = 1;i<=n;i++)
{
maxx = 0;
for(int j = 1;j<=n;j++)
{
if(i==j)
continue;
if(mapp[i][j]> maxx)
{
maxx = mapp[i][j];
}
}
if(ti>maxx)
{
ti = maxx;
st = i;
}
}
if(st!=-1)
printf("%d %d
",st,ti);
else
puts("disjoint");
}
return 0;
}