import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class DijkstraKota {

    // Sisi berbobot: kota tujuan dan jarak tempuh dalam kilometer.
    record Sisi(String tujuan, int jarak) { }

    // Entri antrean prioritas: kota dan jarak sementara terbaik yang diketahui.
    record Entri(String kota, int jarakSementara) { }

    private final Map<String, List<Sisi>> jalan = new LinkedHashMap<>();
    private final Map<String, String> induk = new HashMap<>(); // untuk rekonstruksi rute

    public static void main(String[] args) {
        DijkstraKota peta = new DijkstraKota();
        peta.tambahJalan("Jakarta", "Bandung", 150);
        peta.tambahJalan("Jakarta", "Semarang", 450);
        peta.tambahJalan("Jakarta", "Surabaya", 810);
        peta.tambahJalan("Bandung", "Yogyakarta", 430);
        peta.tambahJalan("Semarang", "Yogyakarta", 125);
        peta.tambahJalan("Semarang", "Surabaya", 350);
        peta.tambahJalan("Yogyakarta", "Surabaya", 260);
        peta.tambahJalan("Surabaya", "Denpasar", 500);
        peta.tambahJalan("Yogyakarta", "Denpasar", 900);

        Map<String, Integer> jarak = peta.jarakTerpendek("Jakarta");
        System.out.println("=== Dijkstra dari Jakarta (jarak dalam km) ===");
        for (Map.Entry<String, Integer> e : jarak.entrySet()) {
            System.out.printf("  %-10s %d km%n", e.getKey(), e.getValue());
        }

        System.out.println();
        System.out.println("Rute ke Denpasar : " + peta.ruteKe("Denpasar"));
        System.out.println("Rute ke Yogyakarta: " + peta.ruteKe("Yogyakarta"));
    }

    void tambahJalan(String dari, String ke, int jarak) {
        jalan.computeIfAbsent(dari, k -> new ArrayList<>()).add(new Sisi(ke, jarak));
        jalan.computeIfAbsent(ke, k -> new ArrayList<>());
    }

    Map<String, Integer> jarakTerpendek(String mulai) {
        Map<String, Integer> jarak = new LinkedHashMap<>();
        Map<String, String> induk = new HashMap<>();
        for (String kota : jalan.keySet()) {
            jarak.put(kota, Integer.MAX_VALUE);
        }
        jarak.put(mulai, 0);

        PriorityQueue<Entri> antrean = new PriorityQueue<>(
                Comparator.comparingInt(Entri::jarakSementara));
        antrean.add(new Entri(mulai, 0));

        while (!antrean.isEmpty()) {
            Entri sekarang = antrean.poll();
            if (sekarang.jarakSementara() > jarak.get(sekarang.kota())) {
                continue; // Entri basi: kota ini sudah ditemukan lewat rute lebih pendek.
            }
            for (Sisi sisi : jalan.get(sekarang.kota())) {
                int kandidat = sekarang.jarakSementara() + sisi.jarak();
                if (kandidat < jarak.get(sisi.tujuan())) {
                    jarak.put(sisi.tujuan(), kandidat);
                    induk.put(sisi.tujuan(), sekarang.kota());
                    antrean.add(new Entri(sisi.tujuan(), kandidat));
                }
            }
        }
        return jarak;
    }

    String ruteKe(String tujuan) {
        List<String> rute = new ArrayList<>(List.of(tujuan));
        String kota = tujuan;
        while (induk.containsKey(kota)) {
            kota = induk.get(kota);
            rute.add(0, kota);
        }
        return String.join(" -> ", rute);
    }
}