[백준 1504번] [Dijkstra] 특정한 최단 경로

Approach

최단 경로의 길이를 물어보는 것에서 다익스트라 문제임을 쉽게 파악할 수 있다.

 

이 문제에서 눈여겨 봐야할 지점은 반드시 거쳐야하는 정점이 있다는 것이다.

잠시 기억을 더듬어서 고등학교 경우의 수 문제에서 최단거리를 구할 때, 특정한 지점을 반드시 지나는 문제를 어떻게 풀었는지를 잘 생각해보자. 아마도 특정한 지점을 기준으로 분할해서 풀었던 기억이 있을 것이다.

 

마찬가지로 위 문제도 특정한 지점을 기준으로 분할해서 풀어주면 된다.

두 정점을 순서대로 v1, v2라고 하고, d(a, b)를 a부터 b까지 가는데 필요한 최단 경로의 길이라고 정의하자

 

d(1, N) = min(d(1, v1) + d(v1, v2) + d(v2, N), d(1, v2) + d(v2, v1) + d(v1, N))이다.

 

이를 보장할 수 있는 이유는 한번 이동했던 간선 및 정점을 다시 방문할 수 있으므로 각각의 경로는 독립적이기 때문이다.

따라서 그리디하게 각 정점까지의 최단 경로를 더해주는 것으로 정답을 도출할 수 있게 된다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef long long ll;
typedef vector <ull> ullv1;
typedef vector <vector <ull> > ullv2;
const int INF = 987654321;


int main() {
    fastio;

    int n, e;
    cin >> n >> e;
    vector<pii> edge[800];

    for(int i = 0; i < e; i++){
        int a, b, c;
        cin >> a >> b >> c;

        edge[a - 1].push_back({b - 1 , c});
        edge[b - 1].push_back({a - 1, c});
    }

    int v1, v2;
    cin >> v1 >> v2;
    v1--;
    v2--;

    tuple<int, int, int> check[3] = {{0, v1, v2},
                       {v1, v2, n - 1},
                       {v2, v1, n - 1}};

    int result[3][2];
    
    for(int i = 0; i < 3; i++){
        int s, to_1, to_2;
        tie(s, to_1, to_2) = check[i];

        int dist[800];
        bool visited[800];
        memset(visited, 0, sizeof(visited));
        fill(dist, dist + 800, INF);
        dist[s] = 0;
        
        priority_queue<pii, vector<pii>, greater<pii> >pq;
        pq.push({0, s});
        while(!pq.empty()){
            int cur = -1;
            while(!pq.empty()){
                if(!visited[pq.top().second]){
                    cur = pq.top().second;
                    pq.pop();
                    break;
                }
                pq.pop();
            }
            if(cur == -1) break;
            visited[cur] = 1;
            for(auto p : edge[cur]){
                int to = p.first, cost = p.second;
                if(dist[cur] + cost < dist[to]){
                    dist[to] = dist[cur] + cost;
                    pq.push({dist[to], to});
                }
            }
        }

        result[i][0] = dist[to_1];
        result[i][1] = dist[to_2];
    }

    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 2; j++){
            if(result[i][j] == INF){
                cout << -1 << "\n";
                return 0;
            }
        }
    }

    cout << min(result[0][0] + result[1][0] + result[2][1], result[0][1] + result[1][1] + result[2][0]) << "\n";
    return 0;    
}