https://www.acmicpc.net/problem/1753

최단경로

주어진 그래프에서 최단경로를 구하는 문제이다.

최단 경로를 구하는 데 있어 여러가지 방법이 있지만 이번 문제에서는 음의 가중치가 없고, 시작점이 주어졌기 때문에 다익스트라 알고리즘을 사용해서 풀이했다.

풀이

최단 거리를 구할 때 방법으로 배열을 이용하는 방법과 우선 순위 큐를 이용하여 구하는 방법 2가지가 있다.

배열을 이용하여 최단거리를 구한다면 연결된 모든 정점을 탐색해야 하기때문에 우선 순위 큐를 이용하여 구현하는 것보다 시간이 오래 걸린다.

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

우선 순위 큐에 간선을 넣을 때 주의할 점이 있다.
우선 순위 큐에 삽입해 정렬을 할 때 기준값은 weight 값으로 오름차순으로 정렬이 된다.

따라서 큐에 삽입할 때 목적지 좌표와 함께 가중치는 해당 목적지까지 가는데 든 가중치의 합이 들어가야 한다.

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

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static boolean[][] visit;
    static int n, m;
    static int ans = 0;
    static int[] chess;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] nums = br.readLine().split(" ");
        n = Integer.parseInt(nums[0]);
        m = Integer.parseInt(nums[1]);
        int k = Integer.parseInt(br.readLine());
        ArrayList<Pair>[] graph = new ArrayList[n + 1];
        PriorityQueue<Pair> queue = new PriorityQueue<>();

        for (int i = 0; i <= n; i++)
            graph[i] = new ArrayList<>();

        int[] distance = new int[n + 1];
        boolean[] visited = new boolean[n + 1];

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            int w = Integer.parseInt(line[2]);
            graph[x].add(new Pair(y, w));
        }

        for (int i = 1; i <= n; i++) {
            if (i == k)
                distance[i] = 0;
            else
                distance[i] = Integer.MAX_VALUE;
        }

        queue.offer(new Pair(k, 0));
        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            int y = p.y;
            if (visited[y])
                continue;
            else
                visited[y] = true;

            for (Pair next : graph[y]) {
                if (distance[next.y] >= distance[y] + next.w) {
                    distance[next.y] = distance[y] + next.w;
                    queue.offer(new Pair(next.y, distance[next.y]));
                }
            }
        }

        for(int i = 1;i<=n;i++) {
            if(distance[i] != Integer.MAX_VALUE)
                System.out.println(distance[i]);
            else
                System.out.println("INF");
        }
        //bw.write(ans + "\n");
        br.close();
        bw.close();
    }
}

class Pair implements Comparable<Pair> {
    public int y;
    public int w;

    public Pair(int y, int w) {
        this.y = y;
        this.w = w;
    }

    @Override
    public int compareTo(Pair o) {
        return Integer.compare(this.w, o.w);
    }
}