题目简答,考floyd算法。代码如下:
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<string.h>
#define INTMAX 10000
using namespace std;int visit[101];
int path[101][101];
int cons[101][101];
int n;void floyd()
{int i,j,k;for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(cons[i][j]>cons[i][k]+cons[k][j])cons[i][j]=cons[i][k]+cons[k][j];
}void find()
{int i,j,max;for(i=0;i<n;i++){max=0;for(j=0;j<n;j++){if(i!=j&&cons[i][j]>max)max=cons[i][j];}visit[i]=max;}
}int main()
{int i,j,m,ano,max;while(cin>>n&&n!=0){memset(visit,0,sizeof(visit));memset(cons,INTMAX,sizeof(cons));for(i=0;i<n;i++)cons[i][i]=0;for(i=0;i<n;i++){cin>>m;for(j=0;j<m;j++){cin>>ano;cin>>cons[i][ano-1];} }floyd();find();max=0;for(i=0;i<n;i++){if(visit[i]==INTMAX){cout<<"disjoint"<<endl;goto L1;}if(visit[i]<visit[max])max=i;}cout<<max+1<<" "<<visit[max]<<endl;
L1: ;}return 0;
}