문제링크

풀이

이전에 플로이드 문제를 풀어서 그런지 이 문제를 보자마자 똑같은 문제 아니야? 하고 같은 방법으로 풀었다가 바로 틀려버렸다. 일단 시간제한도 0.5초로 굉장히 짧다.

우선순위 큐를 사용한 다익스트라를 사용해서 풀이하였다.
해당 알고리즘을 완전히 이해하고 구현할 수 있었다면 금방 풀었을텐데, 그렇지 않아서 다시 공부하고 푸느라 시간이 오래 걸렸다.

코드

package BOJ;

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

public class sol1916 {
    static int n, m;
    static ArrayList<City>[] graph;

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

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        graph = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[start].add(new City(end, cost));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int targetStart = Integer.parseInt(st.nextToken());
        int targetEnd = Integer.parseInt(st.nextToken());
        int[] dist = dijkstra(n, targetStart);
        System.out.println(dist[targetEnd]);
    }

    public static int[] dijkstra(int n, int start) {
        boolean[] visited = new boolean[n + 1]; //  해당 정점을 방문했는지 확인하는 배열
        int[] dist = new int[n + 1];    //  출발지에서 특정 정점까지 최단거리를 저장 및 갱신하기 위한 배열
        int INF = Integer.MAX_VALUE;

        Arrays.fill(dist, INF);
        dist[start] = 0;    //  출발지까지의 거리는 0임.

        PriorityQueue<City> pq = new PriorityQueue<>(); //  현재 정점과 인접한 도시들을 저장
        pq.offer(new City(start, 0));

        while (!pq.isEmpty()) {
            int curr = pq.poll().num;   //  현재 확인하는 도시 번호
            if (visited[curr]) {
                continue;
            }
            visited[curr] = true;
            for (City next : graph[curr]) {
                if (dist[next.num] > dist[curr] + next.cost) {
                    dist[next.num] = dist[curr] + next.cost;
                    pq.offer(new City(next.num, dist[next.num]));
                }
            }
        }
        return dist;
    }

    public static class City implements Comparable<City> {
        int num, cost;

        public City(int num, int cost) {
            this.num = num;
            this.cost = cost;
        }

        @Override
        public int compareTo(City city) {
            return Integer.compare(this.cost, city.cost);
        }
    }
}