[BOJ\GoldIV] 1753. 최단 경로 - JAVA 자바

1753번: 최단경로

• 728ms
• 다익스트라

방향 그래프가 주어지고 출발 노드에서 모든 노드로의 최단 경로를 구하는 문제로 최소힙을 이용한 다익스트라 알고리즘을 구현하면 된다.

 

# 소스코드

import java.io.*;
import java.util.*;

public class Main {
    static class Node implements Comparable<Node> {
        int index;
        int distance;

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

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

    static int v, e, k;
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] d;

    public 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.distance;
            int now = node.index;

            if (dist > d[now]) continue;

            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).distance;

                if (cost < d[graph.get(now).get(i).index]) {
                    d[graph.get(now).get(i).index] = cost;
                    pq.offer(new Node(graph.get(now).get(i).index, cost));
                }
            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(br.readLine());

        d = new int[v + 1];

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

        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())));
        }

        Arrays.fill(d, Integer.MAX_VALUE);

        dijkstra(k);

        for (int i = 1; i <= v; i++) {
            if (d[i] == Integer.MAX_VALUE)
                sb.append("INF");
            else
                sb.append(d[i]);
            sb.append('\n');
        }
        System.out.println(sb);

    }
}