挺水的题，不过解题蛮巧妙，如果没这样想的话可能会挺麻烦
用floyd求出两个点之间的最小距后，判断从每一个点i到所有其他的点的最大值，这个值就是从i开始所需要的时间，判断哪个点时间最短就可以了
#include <iostream> #include <string.h> #include <stdio.h> #define inf 10000 using namespace std; int n,maxend,iend; int map[inf][inf]; void floyd() { for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=j&&map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j]; } } } } void getResult() { maxend=inf; for(int i=1;i<=n;i++) { int fals=0,max=0; for(int j=1;j<=n;j++) { if(map[i][j]==inf) { fals=1; break; } if(map[i][j]>max) max=map[i][j]; } if(fals==1) continue; if(max<maxend) { maxend=max; iend=i; } } } int main() { int m,k,v; while(scanf("%d",&n)&&n!=0) { for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) { map[i][j]=inf; if(i==j) map[i][j]=0; } for(int i=1;i<=n;i++) { scanf("%d",&m); for(int j=1;j<=m;j++) { scanf("%d %d",&k,&v); map[i][k]=v; } } floyd(); getResult(); printf("%d %d\n",iend,maxend); } //cout << "Hello world!" << endl; return 0; } /* 3 2 2 4 3 5 2 1 2 3 6 2 1 2 2 2 */
