NO IMAGE

題目: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 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
輸出樣例:
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;
}
}
}