public class Test1 {
    public static void main(String[] args) {
        System.out.println("請(qǐng)輸入有幾個(gè)頂點(diǎn)：");
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        char[] vertex = new char[n];
        System.out.println("請(qǐng)輸入各個(gè)頂點(diǎn)的符號(hào)，每個(gè)字符用空格分隔：");
        for (int i = 0; i < n; i++) {
            vertex[i] = scanner.next().charAt(0);
        }
        int[][] arr = new int[n][n];
        System.out.println("請(qǐng)輸入各個(gè)頂點(diǎn)在二維表之間的距離，不能直達(dá)的用100表示：");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scanner.nextInt();
            }
        }
        Graph gp = new Graph(vertex, arr, n);
        gp.floyd();
        gp.show(vertex);
    }
}
//創(chuàng)建圖
class Graph {
    private char[] vertex;
    private int[][] dis; // 從頂點(diǎn)出發(fā)到其他節(jié)點(diǎn)的距離
    private int[][] pre; // 目標(biāo)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
    // 頂點(diǎn)數(shù)組 鄰接矩陣 長(zhǎng)度大小
    public Graph(char[] vertex, int[][] dis, int len) {
        this.vertex = vertex;
        this.dis = dis;
        this.pre = new int[len][len];
        // 對(duì)pre數(shù)組進(jìn)行初始化
        for (int i = 0; i < len; i++) {
            Arrays.fill(pre[i], i);
        }
    }
    public void show(char[] vertex) {
        for (int i = 0; i < dis.length; i++) {
            for (int j = 0; j < dis.length; j++) {
                System.out.print(vertex[pre[i][j]] + "  ");
            }
            System.out.println();
            for (int j = 0; j < dis.length; j++) {
                System.out.print("( " + vertex[i] + " -> " + vertex[j] + " 的最短路徑 " + dis[i][j] + " )    ");
            }
            System.out.println();
        }
    }
    // 弗洛伊德算法
    public void floyd() {
        int len = 0;
        // 從中間節(jié)點(diǎn)進(jìn)行遍歷
        for (int k = 0; k < dis.length; k++) {
            // 對(duì)出發(fā)節(jié)點(diǎn)進(jìn)行遍歷
            for (int i = 0; i < dis.length; i++) {
                // 遍歷終點(diǎn)節(jié)點(diǎn)
                for (int j = 0; j < dis.length; j++) {
                    len = dis[i][k] + dis[k][j];
                    if (len < dis[i][j]) {
                        dis[i][j] = len;
                        pre[i][j] = pre[k][j];
                    }
                }
            }
        }
    }
}