[C++] 특정한 최단 경로 (백준 1504번)

https://www.acmicpc.net/problem/1504

 

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

int INTMAX = 1000000;
int n, e, v1, v2;
vector<vector<pair<int, int>>> edge;

int dijkstra(int s, int e) {
    vector<int> dst(n + 1, INTMAX);
    priority_queue<pair<int, int>> pq;

    dst[s] = 0;
    pq.emplace(0, s);

    while (!pq.empty()) {
        int cost = -pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        for (auto nxt: edge[cur]) {
            int newcost = cost + nxt.second;
            if (newcost < dst[nxt.first]) {
                dst[nxt.first] = newcost;
                pq.emplace(-newcost, nxt.first);
            }
        }
    }

    return dst[e];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> e;
    edge = vector<vector<pair<int, int>>>(n + 1);

    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edge[a].emplace_back(b, c);
        edge[b].emplace_back(a, c);
    }

    cin >> v1 >> v2;

    cout << dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, n) << '\n';
}

다익스트라를 함수로 만들어 총 3번 호출하여 총 경로를 계산했다. 처음에 제출했던 코드이다. 도달하지 못하는 경우로 고려하지 않았고 최단 경로가 1 → v2 → v1 → n 인 경우도 고려하지 않았다. (WA)

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

int INTMAX = 10000000;
int n, e, v1, v2;
vector<vector<pair<int, int>>> edge;

int dijkstra(int s, int e) {
    vector<int> dst(n + 1, INTMAX);
    priority_queue<pair<int, int>> pq;

    dst[s] = 0;
    pq.emplace(0, s);

    while (!pq.empty()) {
        int cost = -pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        for (auto nxt: edge[cur]) {
            int newcost = cost + nxt.second;
            if (newcost < dst[nxt.first]) {
                dst[nxt.first] = newcost;
                pq.emplace(-newcost, nxt.first);
            }
        }
    }

    return dst[e];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> e;
    edge = vector<vector<pair<int, int>>>(n + 1);

    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edge[a].emplace_back(b, c);
        edge[b].emplace_back(a, c);
    }

    cin >> v1 >> v2;

    int ans1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, n);
    int ans2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, n);
    if (ans1 >= INTMAX && ans2 >= INTMAX) cout << -1 << '\n';
    else cout << min(ans1, ans2) << '\n';
}

이 문제에서 다익스트라 코드 동작 과정은 다음과 같다. 

 

1. 초기화: 모든 노드의 최단 경로를 매우 큰 값으로 초기 설정하여 아직 방문되지 않았음을 표시한다.
2. 우선순위 큐 사용: 우선순위 큐를 이용해 출발 노드부터 탐색을 시작하며, 거리가 짧은 노드를 먼저 처리하도록 한다. 현재 노드를 큐에서 꺼내어 연결된 인접 노드를 확인한다.
3. 거리 업데이트: 현재 노드를 통해 인접 노드로 가는 새로운 경로가 더 짧으면, 최단 경로 정보를 갱신한다. 갱신된 경로는 다시 우선순위 큐에 넣어 다른 경로보다 우선적으로 처리될 수 있도록 한다.
4. 최종 경로 계산: 1 → v1 → v2 → n 경로와 1 → v2 → v1 → n 노드 경로의 최단 비용을 각각 계산한다. 두 경로 중 최소값을 최종 경로 비용으로 출력하며, 둘 다 불가능할 경우 -1을 출력한다.

(AC)