문제

풀이요약

다익스트라

풀이상세

1. 최단 경로의 알고리즘의 핵심은 부분 경로의 최단 경로가 모여 전체의 최단 경로를 만든다는 것이다. 즉 $a→b→c$ 경로에서 ($a$ : 출발, $c$ : 도착) $a→c$ 까지의 경로는 $a→b$ 의 최단 경로 + $b→c$ 의 최단 경로가 된다.

2. 지나쳐야 하는 노드 $n1$, $n2$ 가 출발과 도착 노드가 아니며, $1$ 과 $N$ 이 각각 출발과 도착을 의미하는 경우, $n1$, $n2$ 는 $1$ 보단 크고 $N$ 보다는 작다는 것을 알 수 있다. 따라서 문제의 임의의 두 노드를 포함한 출발노드 부터 도착노드까지의 최단 경로는 최종적으로 2가지 경우로 나타낼 수 있다

   • 출발 → $n1$ → $n2$ → 도착
   • 출발 → $n2$ → $n1$ → 도착

3. 두 개의 경우 가운데 가장 작은 값을 출력한다. 단, 문제에서 경로가 없는 경우 $-1$ 로 출력하라고 하였다. 따라서 해당 경로가 가장 긴 최단 경로인 2억을 넘거나, 경로가 없는 이유로 $0$ 혹은 $0$ 보다 작은 값이 나오는 경우를 예외 범위로 잡는다.

정답

C++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int N, E;
struct node {
    int next;
    int dist;
};

struct compare {
    bool operator()(node &n1, node &n2) {
        return n1.dist > n2.dist;
    }
};

vector<node> v[804];
int n1, n2, ans1, ans2;
const int INF = 200000001;

void input() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> E;
    int st, ed, d;
    for (int i = 0; i < E; i++) {
        cin >> st >> ed >> d;
        v[st].push_back({ed, d});
        v[ed].push_back({st, d});
    }
    cin >> n1 >> n2;
}

int dijkstra(int st, int ed) {
    priority_queue<node, vector<node>, compare> pq;
    pq.push({st, 0});
    int dist[N+1];
    fill(dist, dist + N + 1, INF);
    dist[st] = 0;
    while (!pq.empty()) {
        node curr = pq.top();
        pq.pop();
        for (node n: v[curr.next]) {
            if (dist[n.next] > n.dist + curr.dist) {
                dist[n.next] = n.dist + curr.dist;
                pq.push({n.next, dist[n.next]});
            }
        }
    }
    return dist[ed];
}

void solve() {
    ans1 = dijkstra(1, n1) + dijkstra(n1, n2) + dijkstra(n2, N);
    ans2 = dijkstra(1, n2) + dijkstra(n2, n1) + dijkstra(n1, N);
}

void output() {
    cout << (min(ans1, ans2) >= INF || min(ans1, ans2) <= 0 ? -1 : min(ans1, ans2));
}

int main() {
    input();
    solve();
    output();
}

JAVA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Node {
        // 진행하는 경로
        int next;
        // 비용
        int cost;

        public Node(int next, int cost) {
            this.next = next;
            this.cost = cost;
        }
    }

    static List<Node>[] map;
    static final int INF = (int) 1e9;
    static int N;
    public static void main(String[] args) throws Exception {
        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());

        map = new ArrayList[N + 1];

        for(int i=1; i<=N; i++) map[i] = new ArrayList<>();

        while(--E>=0) {
            st = new StringTokenizer(br.readLine());
            int prev = Integer.parseInt(st.nextToken());
            int next = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            map[prev].add(new Node(next, cost));
            map[next].add(new Node(prev, cost));
        }

        st = new StringTokenizer(br.readLine());
        int nodeA = Integer.parseInt(st.nextToken());
        int nodeB = Integer.parseInt(st.nextToken());


        
		int case1 = dijkstra(1, nodeA) + dijkstra(nodeA, nodeB) + dijkstra(nodeB, N);
        int case2 = dijkstra(1, nodeB) + dijkstra(nodeB, nodeA) + dijkstra(nodeA, N);

        if (case1 < 0 || case2 < 0 || case1 >= INF || case2 >= INF) System.out.println(-1);
        else System.out.println(Math.min(case1, case2));
    }

    private static int dijkstra(int st, int ed) {
        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> n1.cost - n2.cost);
        boolean[] visited = new boolean[N+1];
        int[] dist = new int[N+1];
        Arrays.fill(dist, INF);

        dist[st] = 0;
        pq.add(new Node(st, 0));

        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            if (visited[curr.next]) continue;
            visited[curr.next] = true;

            for (Node nNode : map[curr.next]) {
                if (dist[nNode.next] > nNode.cost + curr.cost) {
                    dist[nNode.next] = nNode.cost + curr.cost;
                    pq.add(new Node(nNode.next, dist[nNode.next]));
                }
            }
        }

        return dist[ed];
    }