思路:求出一行的最大值,同时求解出一列中的最下值,并记下下标,采用Floyd算法。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxx=1005;
const int inf=0x3f3f3f3f;
int n;
int e[maxx][maxx];
int flag;
void Floy(int n){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){e[i][j]=min(e[i][j],e[i][k]+e[k][j]);}}}
}
int main(){while(cin>>n){if(n==0)break;flag=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j){e[i][j]=0;}else{e[i][j]=inf;}}}for(int i=1;i<=n;i++){int t;cin>>t;for(int j=1;j<=t;j++){int a,time;cin>>a>>time;e[i][a]=time;}}Floy(n);int sum=inf;int maxin;int fast;for(int i=1;i<=n;i++){maxin=0;for(int j=1;j<=n;j++){if(maxin<e[i][j]&&e[i][j]>0){maxin=e[i][j];}}if(maxin<sum){sum=maxin;fast=i;}}if(sum!=inf){cout<<fast<<" "<<sum<<endl;}else{cout<<"disjoint"<<endl;}}return 0;
}