poj1125Stockbroker Grapevine - floyd最短路

poj1125Stockbroker Grapevine

題目生詞比較多...

翻譯如下：

http://poj.org/showmessage?message_id=162255

首先，題目可能有多組測試資料，每個測試資料的第一行為經紀人數量N（當N=0時，輸入資料結束），然後接下來N行描述第i（1<=i<=N）個經紀人與其他經紀人的關系（教你如何畫圖）。

每行開頭數字M為該行對應的經紀人有多少個經紀人朋友（該節點的出度，可以為0），然後緊接着M對整數，每對整數表示成a,b,則表明該經紀人向第a個經紀人傳遞資訊需要b機關時間（即第i号結點到第a号結點的孤長為b），整張圖為有向圖，即弧Vij 可能不等于弧Vji（資料很明顯，這裡是廢話）。當構圖完畢後，求當從該圖中某點出發，将“消息”傳播到整個經紀人網絡的最小時間，輸出這個經紀人号和最小時間。最小時間的判定方式為——從這個經紀人（結點）出發，整個經紀人網絡中最後一個人接到消息的時間。如果有一個或一個以上經紀人無論如何無法收到消息，輸出“disjoint”（有關圖的連通性，你們懂得，但據其他同學說，POJ測試資料中不會有，就是說，你不判定，一樣能過，題目資料夠水的）。

以第一樣例為例：

3

2 2 4 3 5

2 1 2 3 6

2 1 2 2 2

總共3個經紀人，一号經紀人可向2個人傳遞資訊，向2号傳遞所需時間為4分鐘，向3号傳遞需5分鐘。二号經紀人可向2個人傳遞資訊，向1号需2分鐘，向3号需6分鐘。三号經紀人可向2人傳遞資訊，向1号需2分鐘，向2号需2分鐘。

（以上阿拉伯數字即為對應資料）将圖畫出，很容易得出，從3号出發，網絡中最後一個得到消息的，需2分鐘（可以同時向多人傳遞，有點不合情理）。

是以輸出為 3 2。

#include<iostream>
#include<stdio.h>
using namespace std;

#define INF 1000000000
int mp[10][10];//資料太弱了。。。。。

int main()
{
	int N,n,i,j,k,min,max,y,c;
	while(scanf("%d",&N),N)
	{
		for(i=1;i<=N;i++)
			for(j=1;j<=N;j++)
				mp[i][j]=INF;
		for(i=1;i<=N;i++)
		{
			scanf("%d",&n);
			for(j=1;j<=n;j++)
			{
				scanf("%d%d",&y,&c);
				mp[i][y]=c;
			}
			mp[i][i]=0;
		}
		
		for(k=1;k<=N;k++)
			for(i=1;i<=N;i++)
				for(j=1;j<=N;j++)
					if(mp[i][j]>mp[i][k]+mp[k][j])
						mp[i][j]=mp[i][k]+mp[k][j];
		int mark=1;
		min=INF;
		for(i=1;i<=N;i++)
		{
			max=0;
			for(j=1;j<=N;j++)
			if(max<mp[i][j])
				    max=mp[i][j];
			if(min>max)
			{
				min=max;
				mark=i;
			}
		}
		printf("%d %d\n",mark,min);
		}
	return 0;
}