# PTA 5-8 哈利波特的考試 （Java實現）

PTA – 資料結構與演算法題目集（中文） – 5-8

##### 輸入樣例:
``````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];
// 得到鄰接矩陣
// 呼叫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;
}
}
}
``````