문제 - 1504

문제접근

1. 특정 정점에서 다른 정점까지의 최단거리를 구하기 위해선 다익스트라를 사용
2. 특정한 두 정점을 지나가야되므로 특정한 두 정점을 기준으로도 다익스트라를 사용
3. 1 -> v1 -> v2 -> N, 1 -> v2 -> v1 -> N으로 가는 경로 중에서 최단경로를 구함
4. 경로가 없을 경우에는 Integer.MAX_VALUE보다 더 큰 값이 나올 수 있으므로 최대값 정정

소스코드

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

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

        int N = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        ArrayList<Node> graph[] = new ArrayList[N+1];

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

        for(int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[a].add(new Node(b,c));
            graph[b].add(new Node(a,c));
        }
        st = new StringTokenizer(br.readLine());
        int firstNode = Integer.parseInt(st.nextToken());
        int secondNode = Integer.parseInt(st.nextToken());

        int first = 0;

        int second = 0;
        int dist1[] =dijkstra(1,graph,N);
        int distv1[] =dijkstra(firstNode,graph,N);
        int distv2[] =dijkstra(secondNode,graph,N);
        // 1 -> first -> second -> N
        first = dist1[firstNode] + distv1[secondNode] + distv2[N];
        // 1 -> second -> first -> N
        second = dist1[secondNode] + distv2[firstNode] + distv1[N];

        if (dist1[firstNode] == Integer.MAX_VALUE || distv1[secondNode] == Integer.MAX_VALUE || distv2[N] == Integer.MAX_VALUE) {
            first = Integer.MAX_VALUE;
        }

        if (dist1[secondNode] == Integer.MAX_VALUE || distv2[firstNode] == Integer.MAX_VALUE || distv1[N] == Integer.MAX_VALUE) {
            second = Integer.MAX_VALUE;
        }

        int result = Math.min(first,second);
        System.out.println(result >= Integer.MAX_VALUE ? -1 : result);
    }

    public static int[] dijkstra(int start,ArrayList<Node> []graph, int N){
        int dist[] = new int[N+1];

        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>((x,y) ->
                Integer.compare(x.distance,y.distance));
        pq.add(new Node(start,0));

        while(!pq.isEmpty()){

            Node now = pq.poll();

            int number = now.number;

            if(now.distance > dist[number]){
                continue;
            }

            for(Node next : graph[number])
            {
                int newDis = dist[number] + next.distance;
                if(dist[next.number] >  newDis){
                    dist[next.number] = newDis;
                    pq.add(new Node(next.number, newDis));
                }
            }

        }

        return dist;
    }

    static class Node{
        int number;
        int distance;

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