3542585_ac_0ms_444k.cc

来自「ＰＯＪ １１２５己ＡＣ源代码」· CC 代码 · 共 46 行

#include <iostream>
using namespace std;
	
int ttt[102][102];
int main()
{
	int n, s, v, t, min, code;
	while(cin>>n && n!=0)
	{
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				ttt[i][j]=101;
		for(int i=1; i<=n; i++)
			ttt[i][i]=0;
		min=101;
		for(int i=1; i<=n; i++)
		{
			scanf("%d", &s);
			for(int j=1; j<=s; j++)
			{
				scanf("%d %d", &v, &t);
				ttt[i][v]=t;
			}
		}
		for(int u=1; u<=n; u++)
			for(int v=1; v<=n; v++)
				for(int w=1; w<=n; w++)
					if(ttt[v][u]+ttt[u][w]<ttt[v][w])
						ttt[v][w]=ttt[v][u]+ttt[u][w];
		for(int i=1; i<=n; i++)
		{
			int m=-1, c=i;
			for(int j=1; j<=n; j++)
				if(ttt[i][j]>m)
					m=ttt[i][j];
			if(m<min)
			{
				min=m;
				code=i;
			}
		}
		printf("%d %d\n", code, min);
	}
	return 0;
}