[백준 1054] 특정한 최단 경로 - c++ 최단 경로 알고리즘 구현

문제 개요

• 문제 번호: 1054
• 제목: 특정한 최단 경로
• 난이도: 골드 4
• 링크: 백준 1504번

---

문제 설명

무방향 그래프가 주어진다.

정점 1에서 정점 v1과 정점 v2를 통과해 정점 N으로 최단거리로 이동했을때의 거리 값을 구해야한다.

지났던 정점과 간선은 다시 지나갈 수 있다.

정점의 갯수 N(1 <= N <= 8000), 간선의 갯수 E(1 <= E <= 1000)

정점 a에서 정점 b의 거리의 길이 c (1 <= c <= 1000)

반드시 거쳐야하는 정점 v1 (v1 != N), v2 (v2 != 1) (v1 != v2)

하나의 정점과 또다른 하나의 정점 사이 간선은 하나만 존재한다.

---

접근 방법

정점 1에서 정점 V1과 V2중 가장 짧은 거리인 곳으로 이동 후 해당 정점에서 시작해 선택되지 않은 정점V(1~2)로 이동하고 나서 정점 N으로 이동하는 방식을 생각했다.

이때 최단거리 알고리즘인 다익스타 알고리즘을 사용해 정점 1과 정점 V1, V2 각각에 대한 최단거리를 구해 사용하는 방법을 생각했다.

여기서 고민해본 부분이 V1 = 1 or V2 = N인 경우 어떻게 되는지를 생각해보고 정점이 같을 경우 4가지의 케이스를 생각해봤다

1. V1 != 1 && V2 != N
2. V1 = 1 && V2 != N
3. V1 != 1 && V2 = N
4. V1 = 1 && V2 = N

이렇게 4가지의 경우를 고려를 해야하나 생각했지만 어차피 V1=1일때의 1에서 V1으로 이동하는 최단 거리는 0, V2에서 N으로 이동하는 최단 거리는 0이기 때문에 정점이 같을때의 케이스를 나눌 필요가 없다고 생각했다.

정점 1에서 출발하여 V1과 V2중 짧은 거리인 정점으로 이동해 해당 정점에서 선택되지 않은 정점으로 이동한 후 정점 N으로 이동하는 방식은 두가지 경우로 나뉜다.

1. 1 -> V1 -> V2 -> N
2. 1 -> V2 -> V1 -> N

여기서 고려해볼 부분은 한번 지나간 정점과 간선은 다시 지나갈 수 있기 때문에 1 -> N -> V1 -> V2 -> N 이런 경우도 존재할 수 있다.
하지만 이 경우 어차피 다익스트라를 이용한 최단거리를 구했을때 1 -> V1(N을 지나 V1) -> V2(N을 지나 V2) -> N 이렇게 결국 N을 지나고 정점을 갔을때의 경우도 계산되기 때문에 고려할 요소가 아니다.

---

구현 코드

#include<iostream>
#include<queue>
#include<vector>
#include<tuple>
using namespace std;

const int INF = 200000000;
int n, m, v1, v2;

vector<pair<int, int>>adj[805];

vector<int> solve(int st){
    vector<int> d(n+1, INF);
    d[st] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>pq;
    pq.push({d[st], st});

    while(!pq.empty()){
        int cost, cur;
        tie(cost, cur) = pq.top(); pq.pop();
        if(d[cur] != cost) continue;

        for(auto nxt : adj[cur]){
            if(d[nxt.second] <= d[cur] + nxt.first) continue;
            d[nxt.second] = d[cur] + nxt.first;
            pq.push({d[nxt.second], nxt.second});
        }
    }

    return d;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }
    cin >> v1 >> v2;

    vector<int> st_dist = solve(1);
    vector<int> v1_dist = solve(v1);
    vector<int> v2_dist = solve(v2);

    int ans = 0;
    int mn = st_dist[v1] + v1_dist[v2] + v2_dist[n];
    mn = min(mn, st_dist[v2] + v2_dist[v1] + v1_dist[n]);
    ans += mn;

    if(ans >= INF) ans = -1;
    cout << ans;
}