题目链接：点击打开链接
简单的floyd，暴力直接过。
#include <iostream> #include<string.h> using namespace std; const int inf = 0x3f3f3f3f; struct node { int x, y, t; }a, b; int n, dis[105][105]; int main() { while(cin>>n,n) { for(int i = 0;i < 101;i++) for(int j = 0;j < 101; j++) if(i == j) dis[i][j] = 0; else dis[i][j] = inf; for(int i = 1;i <= n;i++) { int m, id, time; cin>>m; while(m--) { cin>>id>>time; dis[i][id] = time; } } for(int k = 1;k <= n;k++) { for(int i = 1;i <= n;i++) for(int j = 1;j <=n;j++) if(dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; } a.t = inf; for(int i = 1;i <= n;i++) { b.t = 0; for(int j = 1;j <= n;j++) { if(dis[i][j] > b.t) { b.t = dis[i][j]; b.x = i; b.y = j; } } if(b.t < a.t) a = b; } if(a.t >= inf) cout<<"disjoint"<<endl; else cout<<a.x<<' '<<a.t<<endl; } return 0; }