public class GraphMatriks {

    public static void main(String[] args) {
        String[] kota = {"Jakarta", "Bandung", "Semarang", "Yogyakarta", "Surabaya"};

        // ===== Graph tak berarah: adjacency matrix =====
        int[][] matriks = new int[kota.length][kota.length];
        tambahSisi(matriks, kota, "Jakarta", "Bandung");
        tambahSisi(matriks, kota, "Jakarta", "Semarang");
        tambahSisi(matriks, kota, "Bandung", "Yogyakarta");
        tambahSisi(matriks, kota, "Semarang", "Yogyakarta");
        tambahSisi(matriks, kota, "Semarang", "Surabaya");
        tambahSisi(matriks, kota, "Yogyakarta", "Surabaya");

        System.out.println("=== Adjacency matrix (graph tak berarah) ===");
        cetakMatriks(kota, matriks);

        int jumlahSisi = 0;
        for (int i = 0; i < kota.length; i++) {
            for (int j = i + 1; j < kota.length; j++) {
                if (matriks[i][j] == 1) {
                    jumlahSisi++;
                }
            }
        }
        System.out.println("Jumlah sisi terhitung dari matriks: " + jumlahSisi);
        System.out.println("Ruang simpan: " + (kota.length * kota.length) + " sel");

        System.out.println();
        System.out.println("=== Matrix berarah berbobot (jarak dalam km) ===");
        int[][] berat = new int[kota.length][kota.length];
        tambahSisiBerat(berat, kota, "Jakarta", "Bandung", 150);
        tambahSisiBerat(berat, kota, "Jakarta", "Semarang", 450);
        tambahSisiBerat(berat, kota, "Bandung", "Yogyakarta", 400);
        tambahSisiBerat(berat, kota, "Semarang", "Yogyakarta", 130);
        tambahSisiBerat(berat, kota, "Semarang", "Surabaya", 350);
        tambahSisiBerat(berat, kota, "Yogyakarta", "Surabaya", 320);
        tambahSisiBerat(berat, kota, "Surabaya", "Jakarta", 780);
        cetakMatriks(kota, berat);
    }

    static int indeks(String[] kota, String nama) {
        for (int i = 0; i < kota.length; i++) {
            if (kota[i].equals(nama)) {
                return i;
            }
        }
        throw new IllegalArgumentException("Kota tidak dikenal: " + nama);
    }

    static void tambahSisi(int[][] m, String[] kota, String a, String b) {
        m[indeks(kota, a)][indeks(kota, b)] = 1;
        m[indeks(kota, b)][indeks(kota, a)] = 1;   // tak berarah: simetris
    }

    static void tambahSisiBerat(int[][] m, String[] kota, String dari, String ke, int jarak) {
        m[indeks(kota, dari)][indeks(kota, ke)] = jarak;   // berarah: satu sel saja
    }

    static void cetakMatriks(String[] kota, int[][] m) {
        System.out.printf("%-12s", "");
        for (String nama : kota) {
            System.out.printf("%-11s", nama);
        }
        System.out.println();
        for (int i = 0; i < kota.length; i++) {
            System.out.printf("%-12s", kota[i]);
            for (int j = 0; j < kota.length; j++) {
                String sel = (m[i][j] == 0) ? "-" : String.valueOf(m[i][j]);
                System.out.printf("%-11s", sel);
            }
            System.out.println();
        }
    }
}