poj 1125 Stockbrook er Graphvine
1819 ワード
http://poj.org/problem?id=1125
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<map>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int N=105;
const int MAX=100000;
int dist[N][N];
int main()
{
//freopen("data.txt","r",stdin);
int n;
while(cin>>n)
{
if(n==0)
break;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dist[i][j]=MAX;//
for(int i=1;i<=n;++i)
{
int m;
cin>>m;
while(m--)
{
int j,d;
cin>>j>>d;
dist[i][j]=d;//
}
}
for(int l=1;l<=n;++l)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(dist[i][l]+dist[l][j]<dist[i][j])//
{
dist[i][j]=dist[i][l]+dist[l][j];
}
}
}
}
int k,MIN=MAX;
for(int i=1;i<=n;++i)
{
int tempnum=0;
for(int j=1;j<=n;++j)
{
if(i!=j)
tempnum=max(tempnum,dist[i][j]);
}
if(tempnum<MIN)//
{
MIN=tempnum;
k=i;
}
}
if(MIN==MAX)
cout<<"disjoint"<<endl;
else
cout<<k<<" "<<MIN<<endl;
}
return 0;
}