백준 1504 특정한 최단 경로 Java [다익스트라]

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

1504번: 특정한 최단 경로

다익스트라로 1 -> v1 -> v2 -> N 과 1 -> v2 -> v1 -> N 중 가능한 짧은 경로를 찾아 출력하면 된다 

 

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

public class Main {
    static int N;
    static List<int[]>[] nodes;
    static final int INF = 700_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        nodes = new List[N+1];
        for (int n = 1; n <= N; n++) {
            nodes[n] = new ArrayList<>();
        }
        for (int e = 0; e < E; e++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            nodes[a].add(new int[]{b, c});
            nodes[b].add(new int[]{a, c});
        }
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
        int sum = dijkstra(v1, v2) + Math.min(dijkstra(1, v1) + dijkstra(v2, N),
                dijkstra(1, v2) + dijkstra(v1, N));
        int result = sum >= INF ? -1 : sum;
        System.out.println(result);
    }

    static int dijkstra(int start, int end) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        boolean[] vtd = new boolean[N+1];
        int[] dist = new int[N+1];
        Arrays.fill(dist, INF);
        dist[start] = 0;
        queue.add(new int[]{start, 0});
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            if (now[0] == end) return dist[end];
            if (vtd[now[0]]) continue;
            vtd[now[0]] = true;
            for (int[] v : nodes[now[0]]) {
                if (dist[v[0]] > now[1] + v[1]) {
                    dist[v[0]] = now[1] + v[1];
                    queue.add(new int[]{v[0], dist[v[0]]});
                }
            }
        }
        return INF;
    }
}

 

INF 8억으로해서 sum이 int 범위 넘어 가는 것을 못 찾아 몇번을 틀린건지 모르겠다

엣지 케이스인 점 2개 있고 간선 없는 경우 sum > INF로해서 틀렸다