7-26 Harry Potter's Exam（25 point(s))(Floyd算法)

7-26 Harry Potter's Exam（25 point(s)）

In Professor McGonagall's class of Transfiguration, Harry Potter is learning how to transform one object into another by some spells. He has learnt that, to turn a cat into a mouse one can say

docamo

! To reverse the effect, simply say

decamo

! Formally speaking, the transfiguration spell to transform between object A and object B is said to be

S

if there are two spells,

doS

and

deS

, to turn A into B and vice versa, respectively.

In some cases, short-cut spells are defined to make transfiguration easier. For example, suppose that the spell to transform a cat to a mouse is

docamo

, and that to transform a mouse into a fatmouse is

dofamo

, then to turn a cat into a fatmouse one may say

docamodofamo

! Or if a shot-cut spell is defined to be

cafam

, one may get the same effect by saying

docafam

!

Time is passing by quickly and the Final Exam is coming. By the end of the transfiguration exam, students will be requested to show Professor McGonagall several objects transformed from the initial objects they bring to the classroom. Each of them is allowed to bring 1 object only.

Now Harry is coming to you for help: he needs a program to select the object he must take to the exam, so that the maximum length of any spell he has to say will be minimized. For example, if cat, mouse, and fatmouse are the only three objects involved in the exam, then mouse is the one that Harry should take, since it will take a 6-letter spell to turn a mouse into either a cat or a fatmouse. Cat is not a good choice since it will take at least a 7-letter spell to turn it into a fatmouse. And for the same reason Harry must not take a fatmouse.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N (≤100) and M, which are the total number of objects involved in the exam and the number of spells to be tested, respectively. For the sake of simplicity, the objects are numbered from 1 to N. Then M lines follow, each contains 3 integers, separated by a space: the numbers of two objects, and the length of the spell to transform between them.

Output Specification:

For each test case, print in one line the number of the object which Harry must take to the exam, and the maximum length of the spell he may have to say. The numbers must be separated by a space.

If it is impossible to complete all the transfigurations by taking one object only, simply output 0. If the solution is not unique, output the one with the smallest number.

Sample Input:

6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
           

Sample Output:

4 70

思路：這道題其實是用弗洛伊德算法求每個點到其他各點的最短路徑，然後選擇出，以哪個點位起點時，它到各點的最短路徑中最長的那一條，和以其他點為起點最長的那一條
相比最短
有以下幾點注意！！：物品不能變自己，是以循環中如果到了自己變自己的跳過即可，其次，每個物品都能變成其他物品，如果以某個物品不能變成其中的一個物品，那麼這個物
品不符合，直接可以中斷這次循環，判斷以下一個物品為起點
code：
             
//題意是在所有點中尋找一個點，使得這個點到其他所有點的最短路徑中最大的那條邊長度是和其他相比最小的
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
int n,m;
int mp[105][105];
void Floyd(){
	int i,j,k;
	for(k = 1; k <= n; k++){
		for(i = 1; i <= n; i++){
			for(j = 1; j <= n; j++){
				if(mp[i][k] != INF && mp[k][j] != INF && mp[i][j] > mp[i][k] + mp[k][j]){ 
					mp[i][j] = mp[i][k] + mp[k][j];
				}
			}
		}
	}
}
int main(){
	int i,j;
	scanf("%d%d",&n,&m);
	memset(mp,INF,sizeof(mp));
	for(i = 0; i < m; i++){
		int a,b,d;
		scanf("%d%d%d",&a,&b,&d);
		mp[a][b] = mp[b][a] = d;//由題意可知正反都是可以的，是無向圖 
	}
	Floyd();//弗洛伊德算法，求每個點到其他所有點的最短路徑 
	int min = INF;
	int f = -1;//記錄物品編号
	for(i = 1; i <= n; i++){//以每個點作為起點枚舉 
		int max = 0;
		int flag = 1;
		for(j = 1; j <= n; j++){
			if(j == i)//自己不能變成自己，是以跳過 
			   continue;
			if(mp[i][j] == INF){//如果有不能變的，說明這個不行 
				flag = 0;
				break;
			}
			if(mp[i][j]>max){//尋找以i為起點到其他各點的最短路徑中最長的 
				max = mp[i][j];
			}
		}
		if(!flag)
		   continue;
		else{
			if(max != 0 && max < min){//如果這條以i為起點的最長路徑和以其他點為起點的最長路徑比短，更新min，記錄物品編号 
				min = max;
				f = i;
		    }
		} 
	}
	if(min==INF)printf("0\n");
	else{
		printf("%d %d\n",f,min);
	}
	return 0;
}