최단경로 - 1753번

---

풀이 방법

전형적인 다익스트라 문제이다.

우선순위 큐를 이용한 다익스트라 알고리즘을 구현해서 풀이했다.

2021.10.01 - [분류 전체보기] - 최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜)

 

내 코드

package com.company;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Node implements Comparable<Node> {

    private int distance;
    private int index;

    public Node(int index, int distance) {
        this.distance = distance;
        this.index = index;
    }

    public int getDistance() {
        return distance;
    }

    public int getIndex() {
        return index;
    }

    @Override
    public int compareTo(Node other) {
        if (this.distance < other.getDistance())
            return -1;
        return 1;
    }
}

public class Main {
    static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();

    static int v, e, start;

    static int[] d;

    static void dijkstra(int start) {

        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.offer(new Node(start, 0));

        d[start] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int dist = node.getDistance();
            int nowIndex = node.getIndex();

            if (d[nowIndex] < dist)
                continue;

            for (int i = 0; i < graph.get(nowIndex).size(); i++) {
                int cost = d[nowIndex] + graph.get(nowIndex).get(i).getDistance();
                if (cost < d[graph.get(nowIndex).get(i).getIndex()]) {
                    d[graph.get(nowIndex).get(i).getIndex()] = cost;
                    pq.offer(new Node(graph.get(nowIndex).get(i).getIndex(), cost));
                }
            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());

        d = new int[v + 1];

        for (int i = 0; i <= v; i++) {
            graph.add(new ArrayList<Node>());
        }

        Arrays.fill(d, (int) 1e9);

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            graph.get(Integer.parseInt(st.nextToken())).
                    add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        dijkstra(start);

        for (int i = 1; i < d.length; i++) {
            if (d[i] == (int) 1e9)
                System.out.println("INF");
            else
                System.out.println(d[i]);
        }
    }
}