学步园

如有错误，请留言提醒，不要坑到小朋友

Description

China历史最伟大的SPY金无命潜入了美国的FBI，为了整掉这个罪恶的机构，他决定在FBI散布假消息。他首先选定FBI中的某一个职员，将谣言告诉他，然后这个人会将消息再告诉给每一个他认识的人，当然在这个过程中需要花费一定的时候。然后这些人又会把消息告诉给每一个他所认识的人。这样消息就可能传遍整个FBI,当然每个人知道这个消息的时间有先有后。我们希望最晚才知道这个消息的人他所需要的时间越短越好（设这个时间长度为T）。那么金无命应该选择哪一个人做为消息的首发者呢？请输出这个人的编号及T。如果消息不能传遍FBI请输出"disjoint" 
注意从职员A传播谣言给职员B的时间不一定等于从职员B传播谣言给职员A的时间。 

Input

先给出FBI中有多少个职员，用数字N(N<=100)来代表。 
接下来N行，用来描述这N个职员。 
每一行给出这个职员他认识几个人，然后给出所认识的职员的编号及传消息给他所要花的时间. 

Output

如题

Sample Input

3
2 2 4 3 5
2 1 2 3 6
2 1 2 2 2

Sample Output

3 2

Source

这题一看就是Floyd

#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#define maxn 110
#define inf 0x7fffffff
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int w[maxn][maxn],n;
int main(){
	scanf("%d",&n);
	memset(w,63,sizeof(w));
	for(int i=1;i<=n;i++){
		int a,b,q;
		scanf("%d",&q);
		for(int k=1;k<=q;k++){
			scanf("%d%d",&a,&b);
			w[i][a]=min(w[i][a],b);
		}
	}
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			
			if(i!=j&&i!=k&&j!=k)
			w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
	int ans=inf,ansn;
	for(int i=1;i<=n;i++){
		int tmp=0;
		for(int j=1;j<=n;j++)if(i!=j){
			tmp=max(tmp,w[i][j]);
		}
	//	printf("%d %d\n",i,tmp);
		if(tmp<1000000000&&ans>tmp){
			ans=tmp;
			ansn=i;
		}
	}
	if(ans>1000000000)puts("disjoint");
	else printf("%d %d\n",ansn,ans);
//	system("pause");
}