[Wikioi 1020]孿生蜘蛛

題目描述 Description

在G城保衛戰中，超級孿生蜘蛛Phantom001和Phantom002作為第三層防衛被派往守護内城南端一帶極為隐秘的通道。

根據防護中心的消息，敵方已經有一隻特種飛蛾避過第二層防衛，直逼内城南端通道入口。但優秀的蜘蛛已經在每個通道内埋下了堅固的大網，無論飛蛾進入哪個通道，他隻有死路一條！（因為他是無法掙脫超級蛛網的）

現在，001和002分别駐紮在某兩個通道内。各通道通過内線相通，通過每條内線需要一定的時間。當特種飛蛾被困某處，001或002會迅速趕來把它結果掉（當然是耗時最少的那個）。

001跟002都想盡早的完成任務，他們希望選擇在最壞情況下能盡早完成任務的方案。

輸入描述 Input Description

第一行為一個整數N (N<=100) 表示通道數目。

接下來若幹行每行三個正整數a,b,t 表示通道a,b有内線相連，通過的時間為t。(t<=100)

（輸入保證每個通道都直接/間接連通）

輸出描述 Output Description

兩個不同的整數x1,x2，分别為001，002駐紮的地點。（如果有多解，請輸出x1最小的方案，x1相同則輸出x2最小的方案）

樣例輸入 Sample Input

3

1 2 5

2 3 10

3 1 3

樣例輸出 Sample Output

1 2

資料範圍及提示 Data Size & Hint

裸Floyd題，不過在Floyd求出各點間最短路後，還得根據題意枚舉一遍兩個蜘蛛的出發點，求出兩個蜘蛛到它們最遠的點（最壞情況）的最快時間，然後輸出就OK了，另外要注意下題目描述不清，第一行的n不是指有n條邊，而是n個點，後面有若幹行資料，用while()語句寫輸入

#include <stdio.h>
#include <string.h>
#define MAXN 500
#define INF 10000000
int g[MAXN][MAXN],n; //g[i][j]=從i到j的最短路
int min(int a,int b)
{
	if(a<b)
		return a;
	return b;
}
void init()
{
	int a,b,t;
	memset(g,-1,sizeof(g));
	scanf("%d",&n);
	while(scanf("%d%d%d",&a,&b,&t)!=EOF)
	{
		g[a][b]=t;
		g[b][a]=t;
	}
}
void floyd() //求各點間最短路徑
{
	int i,j,k;
	for(k=1;k<=n;k++)
	{
		for(i=1;i<=n;i++)
		{
			if(i!=k)
			{
				for(j=1;j<=n;j++)
				{
					if(i!=j&&j!=k&&g[i][k]!=-1&&g[k][j]!=-1)
					{
						if(g[i][j]>g[i][k]+g[k][j]||g[i][j]==-1)
							g[i][j]=g[i][k]+g[k][j];
					}
				}
			}
		}
	}
}
int getmax(int a,int b) //獲得以蜘蛛在a、b兩點找到飛蛾的最壞情況(兩點各到另一點的距離最小值 的最大值)
{
	int i,f=0;
	for(i=1;i<=n;i++)
		if(min(g[a][i],g[b][i])>f)
			f=min(g[a][i],g[b][i]);
	return f;
}
void solve() //枚舉兩個蜘蛛出現的所有可能位置的最壞情況getmax最小值
{
	int a,b,minn=INF,mina,minb;
	for(a=1;a<=n;a++)
	{
		for(b=1;b<=n;b++)
		{
			if(a!=b)
			{
				if(getmax(a,b)<minn)
				{
					mina=a;
					minb=b;
					minn=getmax(a,b);
				}
			}
		}
	}
	printf("%d %d\n",mina,minb);
}
int main()
{
	init();
	floyd();
	solve();
	return 0;
}