【UOJ 38】 股票经济人通信网络

【题目描述】：

有N个股票经济人可以互相传递消息，他们之间存在一些单向的通信路径。现在有一个消息要由某个人开始传递给其他所有人，问应该由哪一个人来传递，才能在最短时间内让所有人都接收到消息。若不存在这样一个人，则输出disjoint。
【输入描述】：

第一行为n，代表总人数，当n=0时结束程序。

接着n行，第i+1行的第一个是一个整数t，表示第i个人可以传递消息给t个人，接着有t对整数，每对的第一个数是j，表示i可以传递消息给j，第二个数是从i直接传递消息到j所用的时间。
【输出描述】：

两个整数，第一个为选点的散布消息的起点，第二个整数时所有人得知消息的最短时间
【样例输入】：

3
2 2 4 3 5
2 1 2 3 6
2 1 2 2 2
5
3 4 4 2 8 5 3
1 5 8
4 1 6 4 10 2 7 5 2
0
2 2 5 1 5
0

【样例输出】：

3 2
3 10

【时间限制、数据范围及描述】：

时间：1s 空间：128M

N<=300

题解：我jjj吹爆floyd！！！n在300内用floyd太舒服了哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈嗝——。咳咳咳，介入正题，模拟一下啦、如果1到2需要520s，1到3需要250s，则1传递的时间应该是520s，可以同时传递，所以是max不是min，想了好久，最后还是问我身后的dalao(yxr)的！[蒟蒻，哭]

代码：

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int oo=2147483647;
int n,t,x,k;
int f[305][305];
int main(){
    freopen("38.in","r",stdin);
    freopen("38.out","w",stdout);
    while(1){
        scanf("%d",&n);
        if(n==0) break;
        memset(f,0x3f,sizeof(f));
    //  for(int i=1;i<=300;i++)
        //    f[i][i]=0;    
        for(int i=1;i<=n;i++){
            scanf("%d",&t);
            for(int j=1;j<=t;j++){
                scanf("%d %d",&x,&k);
                f[i][x]=k;
            }
        }
        for(int i=1;i<=300;i++)
            f[i][i]=0;   
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

        int mn=oo,ans=0;
        for(int i=1;i<=n;i++){
            int u=0;
            for(int j=1;j<=n;j++)
                u=max(u,f[i][j]);
            if(u<mn)
              { mn=u; ans=i; }
        }
        if(ans==0) printf("disjoint
");
        else printf("%d %d
",ans,mn);
    }
    return 0;
}