題目：http://pta.patest.cn/pta/test/15/exam/4/question/716

PTA - 數據結構與算法題目集（中文） - 5-8

哈利·波特要考試了，他需要你的幫助。這門課學的是用魔咒將一種動物變成另一種動物的本事。例如將貓變成老鼠的魔咒是haha，將老鼠變成魚的魔咒是hehe等等。反方向變化的魔咒就是簡單地將原來的魔咒倒過來念，例如ahah可以將老鼠變成貓。另外，如果想把貓變成魚，可以通過念一個直接魔咒lalala，也可以將貓變老鼠、老鼠變魚的魔咒連起來念：hahahehe。

現在哈利·波特的手里有一本教材，里面列出了所有的變形魔咒和能變的動物。老師允許他自己帶一只動物去考場，要考察他把這只動物變成任意一只指定動物的本事。于是他來問你：帶什么動物去可以讓最難變的那種動物（即該動物變為哈利·波特自己帶去的動物所需要的魔咒最長）需要的魔咒最短？例如：如果只有貓、鼠、魚，則顯然哈利·波特應該帶鼠去，因為鼠變成另外兩種動物都只需要念4個字符；而如果帶貓去，則至少需要念6個字符才能把貓變成魚；同理，帶魚去也不是最好的選擇。

輸入格式:

輸入說明：輸入第1行給出兩個正整數N (≤100)和M，其中N是考試涉及的動物總數，M是用于直接變形的魔咒條數。為簡單起見，我們將動物按1~N編號。隨后M行，每行給出了3個正整數，分別是兩種動物的編號、以及它們之間變形需要的魔咒的長度(≤100)，數字之間用空格分隔。

輸出格式:

輸出哈利·波特應該帶去考場的動物的編號、以及最長的變形魔咒的長度，中間以空格分隔。如果只帶1只動物是不可能完成所有變形要求的，則輸出0。如果有若干只動物都可以備選，則輸出編號最小的那只。

輸入樣例:

6 113 4 701 2 15 4 502 6 505 6 601 3 704 6 603 6 805 1 1002 4 605 2 80
輸出樣例:
4 70
package harry.potter;import java.util.Scanner;public class Demo1 {	static Scanner sc = null;	public static void main(String[] args) {		sc = new Scanner(System.in);		int N = sc.nextInt();		int M = sc.nextInt();		int[][] G = new int[N][N];		// 得到鄰接矩陣		getAdjacentMatrix(G, M);		// 調用floyd算法		floyd(G);		// //打印出G矩陣		// for(int i=0;i<N;i++){		// for(int j=0;j<N;j++){		// System.out.PRint(G[i][j]+" ");		//		// }		// System.out.println();		// }		// 接下來找到G矩陣中每行的最大值，存入矩陣dist[N]		int[] dist = new int[N];		findLineMaxNum(G, dist);		int minAnimalNum = findMinNum(dist) + 1;		System.out.println("最小動物是" + minAnimalNum + ";最長變形魔咒長度是：" + dist[minAnimalNum - 1]);		sc.close();	}	private static int findMinNum(int[] dist) {		int N = dist.length;		// 把minNum設置成一個很大的數		int minNum = 10000;		int minAnimalNum = 0;		for (int i = 0; i < N; i++) {			if (minNum > dist[i]) {				minNum = dist[i];				minAnimalNum = i;			}		}		System.out.println(minAnimalNum);		return minAnimalNum;	}	public static void findLineMaxNum(int[][] G, int[] dist) {		int maxNum = 0;		int N = G.length;		for (int i = 0; i < N; i++) {			//每次循環maxNum都必須重新置為0			maxNum = 0;			for (int j = 0; j < N; j++) {				if (G[i][j] > maxNum) {					maxNum = G[i][j];				}			}			dist[i] = maxNum;		}	}	// floyd算法	private static void floyd(int[][] G) {		int N = G.length;		for (int k = 0; k < N; k++) {			for (int i = 0; i < N; i++) {				for (int j = 0; j < N; j++) {					if (G[i][k] + G[k][j] < G[i][j]) {						//注意：因為是無向的，所以是對稱矩陣！						G[i][j] = G[i][k] + G[k][j];						G[j][i] = G[i][k] + G[k][j];					}				}			}		}	}	public static void getAdjacentMatrix(int[][] G, int M) {		int N = G.length;		// 把矩陣初始值設為一個很大的值，這里選用100		for (int i = 0; i < N; i++) {			for (int j = 0; j < N; j++) {				if (i != j) {					G[i][j] = 10000;				}			}		}		// 生成鄰接矩陣		int m = 0;		int n = 0;		int num = 0;		for (int i = 0; i < M; i++) {			m = sc.nextInt() - 1;			n = sc.nextInt() - 1;			num = sc.nextInt();			G[m][n] = num;			G[n][m] = num;		}	}}