[필수 문제] 특정 최단거리

1. 문제

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

---

입력

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

출력

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

 

 

 

2. 풀이

이 문제에서 주의해야할 점은 필수적으로 지나가야하는 노드이다.

 

필수로 거쳐야하는 노드 a, b가 있을 때,

• 1번 노드에서 a까지, a에서 b까지, b에서 마지막 노드까지의 최단거리
• 1번 노드에서 b까지, b에서 a까지, a에서 마지막 노드까지의 최단거리

 

이 2개를 비교하여 가장 적은 거리를 출력해주면 된다.

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

class Node implements Comparable<Node>{
    private int node;
    private int weight;

    public Node(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }

    public int getNode() {
        return node;
    }

    public int getWeight() {
        return weight;
    }

    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}

class Graph {
    private ArrayList<ArrayList<Node>> graph;

    public Graph(int nodeSize) {
        graph = new ArrayList<>();

        for(int i = 0; i < nodeSize + 1; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public ArrayList<Node> getNode(int n) {
        return graph.get(n);
    }

    public void put(int n, int m, int weight) {
        graph.get(n).add(new Node(m, weight));
        graph.get(m).add(new Node(n, weight));
    }
}

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int m;

    private static Graph graph;
    private static int[] dist;
    private static boolean[] isVisited;

    private final static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new Graph(n);
        dist = new int[n + 1];
        isVisited = new boolean[n + 1];

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.put(a, b, w);
        }

        st = new StringTokenizer(br.readLine());
        int requiredNode1 = Integer.parseInt(st.nextToken());
        int requiredNode2 = Integer.parseInt(st.nextToken());

        // 노드 1에서 필수 노드 1까지의 최단 거리
        int result1 = 0;
        result1 += dijkstra(1, requiredNode1);
        // 필수 노드 1에서 필수 노드 2까지의 거리
        result1 += dijkstra(requiredNode1, requiredNode2);
        // 필수 노드 2에서 마지막 노드까지의 거리
        result1 += dijkstra(requiredNode2, n);

        // 노드 1에서 필수 노드 2까지의 최단 거리
        int result2 = 0;
        result2 += dijkstra(1, requiredNode2);
        // 필수 노드 2에서 필수 노드 2까지의 거리
        result2 += dijkstra(requiredNode2, requiredNode1);
        // 필수 노드 1에서 마지막 노드까지의 거리
        result2 += dijkstra(requiredNode1, n);

        if(result1 >= INF && result2 >= INF) bw.write("-1\n");
        else bw.write(Math.min(result1, result2) + "");

        br.close();
        bw.flush();
        bw.close();
    }

    private static int dijkstra(int s, int e) {
        Arrays.fill(dist, INF);
        Arrays.fill(isVisited, false);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(s, 0));
        dist[s] = 0;

        while(!pq.isEmpty()) {
            Node curPoint = pq.poll();
            int curNode = curPoint.getNode();
            int curWeight = curPoint.getWeight();

            if(!isVisited[curNode]) {
                isVisited[curNode] = true;

                for(int i = 0; i < graph.getNode(curNode).size(); i++) {
                    int nextNode = graph.getNode(curNode).get(i).getNode();
                    int nextWeight = graph.getNode(curNode).get(i).getWeight();

                    if(!isVisited[nextNode] && dist[nextNode] > curWeight + nextWeight) {
                        dist[nextNode] = curWeight + nextWeight;
                        pq.add(new Node(nextNode, dist[nextNode]));
                    }
                }
            }
        }
        return dist[e];
    }

}