[AJ/Graph] 특정 최단 거리

문제

무방향 그래프가 주어질 때, 정점 1번에서 정점 N번으로 가는 최단거리를 구하려 하는데, 그 과정에서 두 개의 정점을 반드시 거쳐야 한다. 한 번 방문했던 정점을 또 다시 방문하는 것도 허용하고, 간선도 마찬가지로 여러번 방문하는 것을 허용한다고 할 때, 1번에서 N번으로 가는 “특정한" 최단거리를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b, c로 이루어져 있으며, 이는 정점 a와 정점 b가 가중치 c인 간선으로 연결되어 있다는 의미이다. 마지막 줄에는 반드시 거쳐야 하는 두 정점 A, B가 주어진다. ( 1 ≤ a, b, A, B ≤ 1,000, 1 ≤ c ≤ 50,000 )

출력

1번 정점에서 N번 정점으로 가는 “특정한" 최단거리를 출력한다. 단, “특정한" 최단거리란, 주어진 정점 A와 B를 반드시 방문할 때의 최단거리를 의미한다.

예제 입력

4 6 1 2 3 2 3 3 3 4 1 1 3 5 2 4 5 1 4 4 2 3

예제 출력

7

---

풀이

1. 이웃하는 두 정점에 간선이 하나 이상있을 수 있다.

2. 우선순위 큐 사용 

코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n;
    static int dist[][];
    static int map[][];

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        map = new int[n + 1][n + 1];
        dist = new int[3][n + 1];

        for (int i = 0; i < 3; i++)
            Arrays.fill(dist[i], Integer.MAX_VALUE);

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            if(map[a][b]==0) {
                map[a][b] = c;
                map[b][a] = c;
            }else {    //이웃하는 두 정점에 간선이 하나 이상일 수 있다. 
                map[a][b] = Math.min(map[a][b], c);
                map[b][a] = Math.min(map[b][a], c);
            }

        }
        int a = sc.nextInt();
        int b = sc.nextInt();

        dijkstra(1, 0);
        dijkstra(a, 1);
        dijkstra(b, 2);

        long d1 = dist[0][a] + dist[1][b] + dist[2][n];
        long d2 = dist[0][b] + dist[2][a] + dist[1][n];
        long result = 0;
        if (d1 >= Integer.MAX_VALUE)
            result = d2;
        else if (d2 >= Integer.MAX_VALUE)
            result = d1;
        else
            result = Math.min(d1, d2);

        System.out.println(result);
    }

    static void dijkstra(int start, int idx) {
        dist[idx][start] = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>();
        q.add(start);
        while (!q.isEmpty()) {
            int tmp = q.poll();
            for (int i = 1; i <= n; i++) {
                if (map[tmp][i] != 0 && dist[idx][i] > dist[idx][tmp] + map[tmp][i]) {
                    dist[idx][i] = dist[idx][tmp] + map[tmp][i];
                    q.add(i);
                }

            }

        }

    }

}