纯裸的folyd，但是题意太难了，看了半天没看懂，还是google的题意。
// // main.cpp // Richard // // Created by 邵金杰 on 16/8/15. // Copyright © 2016年 邵金杰. All rights reserved. // #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int maxn=100+5; const int INF=100000000; int N; int map[maxn][maxn]; void Input() { for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if(i==j) map[i][j]=0; else map[i][j]=INF; } } for(int i=1;i<=N;i++) { int t,e,w; scanf("%d",&t); for(int j=1;j<=t;j++) { scanf("%d%d",&e,&w); map[i][e]=w; } } } void folyd() { for(int k=1;k<=N;k++) { for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { map[i][j]=min(map[i][j],map[i][k]+map[k][j]); } } } } void Output() { int Min=INF,p=0; for(int i=1;i<=N;i++) { int Max=-INF,position=0; for(int j=1;j<=N;j++) { if(i==j) continue; if(Max<map[i][j]) { Max=map[i][j]; position=i; } } if(Min>Max) {Min=Max;p=position;} } printf("%d %d\n",p,Min); } int main() { while(scanf("%d",&N)&&N) { Input(); folyd(); Output(); } return 0; }