[BOJ 1504 // C++] 특정한 최단경로

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1504번 문제인 특정한 최단경로이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

이 문제는 1번 노드에서 v1, v2번 노드를 거쳐 N번 노드로 가는 최단 경로를 구하는 것이다. 이 때, v1, v2 중 어떤 것을 먼저 들러야 하는지는 알 수 없다.

 

따라서, 1 -> v1 -> v2 -> N번 노드로 가는 경로와 1 -> v2 -> v1 -> N번 노드로 가는 경로를 비교해 더 거리가 짧은 쪽의 거리를 출력하면 된다.

 

만약 1, v1, v2, N번 노드가 같은 component 위에 있지 않다면 위와 같은 경로는 나올 수가 없다. 따라서 이와 같은 경우는 확인을 따로 하고 예외처리를 해주어야 한다. (dijkstra 함수에서 도달 불가능한 경우 불가능한 INF값을 그대로 return하고, 출력 시점에서 거리가 INF 이상으로 크게 나오면 불가능하다는 출력을 해주어도 좋다.)

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using std::cin;
using std::cout;
using std::vector;
using std::pair;
using std::priority_queue;
using std::min;

int N, E; // 정점 개수 N, 간선 개수 E

vector<pair<int, int>> G[801]; // 그래프

int dijkstra(int s, int e) { // dijkstra 함수: s에서 e로 가는 최단거리를 return, 없다면 -1을 return
    int dist[801];
    for (int i = 1;i <= N;i++) dist[i] = 10000000;
    bool done[801];
    for (int i = 1;i <= N;i++) done[i] = false;
    dist[s] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({ 0,s });
    while (!pq.empty()) {
        int current = pq.top().second; pq.pop();
        if (done[current]) continue; // s에서 e로 갈 수 있다면 dijkstra 알고리즘을 돌리면서 만날 수밖에 없다.
        else if (current == e) return dist[current];
        done[current] = true;
        for (auto following : G[current]) {
            int followingnode = following.first;
            int followingweight = following.second;
            if (dist[followingnode] > dist[current] + followingweight) {
                dist[followingnode] = dist[current] + followingweight;
                pq.push({-dist[followingnode],followingnode});
            }
        }
    }
    return -1; // while문에서 e를 만나지 못했으므로 s에서 e로 갈 수 없음을 알 수 있다.
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> E;

    for (int i = 0;i < E;i++) {
        int a, b, w;
        cin >> a >> b >> w;
        G[a].push_back({b,w});
        G[b].push_back({a,w}); // 방향성이 없는 그래프이므로 양방향을 넣는다.
    }
    int v1, v2;
    cin >> v1 >> v2;

    int d1v1 = dijkstra(1, v1); // 변수명은 "distance from (node1) to (node2)" 의 의미로 지었다.
    int d1v2 = dijkstra(1, v2);
    int dv1v2 = dijkstra(v1, v2);
    int dv1N = dijkstra(v1, N);
    int dv2N = dijkstra(v2, N);
    // 아래 중 하나라도 -1이라면 1, v1, v2, N은 하나의 component 위에 있지 않다
    if (d1v1 == -1 or d1v2 == -1 or dv1N == -1 or dv2N == -1) cout << -1; 
    // 아니라면 1, v1, v2, N은 하나의 component 위에 있다.
    else cout << min(d1v1 + dv1v2 + dv2N, d1v2 + dv1v2 + dv1N); 

    return 0;
}