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

문제링크

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

풀이방법

해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다.

• 우선 solve라는 함수를 만들고 int st, int en을 추가해서 st 부터 en까지 최단 거리 값을 알려주는 함수를 만든다.
• 1~N까지의 경로 중에 v1과 v2를 반드시 지나는 경우는 딱 두 가지 케이스가 존재한다.
  (~~~ 중간에 다른 경로를 의미한다. 중간에 다른 경로가 없을 수도 있다.)
  (1) 1~~~V1을 지나고 V1부터 ~~~ V2를 거쳐서 V2~~~n에 도달하는 방법
  (2) 1~~~V2를 지나고 V2부터 ~~~ V1을 거쳐서 V1~~~n에 도달하는 방법
  위 두 케이스만 존재한다.
• 두 케이스에서 작은 값을 최종 결과 값에 넣는다.
• 만약에 결과 값이 INF보다 크다면 해당 경로는 존재하지 않으므로 -1을 출력하고 아닌경우 최종 결과 값이 최소 값이므로 해당 값을 출력한다.

코드

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int n, e, v1, v2;


vector<pair<int, int>> adj[1005]; // {거리, 정점 번호}
const int INF = 0x3f3f3f3f;

long long solve(int st, int en)
{
    int d[1005];
    fill(d, d + n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
    d[st] = 0;
    // 우선순위 큐에 (0, 시작점) 추가
    pq.push({ d[st],st });
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop(); // {거리, 정점 번호}    
        // 거리가 d에 있는 값과 다를 경우 넘어감
        if (d[cur.Y] != cur.X) continue;
        for (auto nxt : adj[cur.Y]) {
            if (d[nxt.Y] <= d[cur.Y] + nxt.X) continue;
            // cur를 거쳐가는 것이 더 작은 값을 가질 경우
            // d[nxt.Y]을 갱신하고 우선순위 큐에 (거리, nxt.Y)를 추가
            d[nxt.Y] = d[cur.Y] + nxt.X;
            pq.push({ d[nxt.Y],nxt.Y });
        }
    }
    return d[en];
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> e;
    
    while (e--) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({ c,b });
        adj[b].push_back({ c,a });
    }
    cin >> v1 >> v2;


    long long ans1 = solve(1, v1) + solve(v1, v2) + solve(v2, n);
    long long ans2 = solve(1, v2) + solve(v2, v1) + solve(v1, n);
    long long ans = min(ans1, ans2);
    if (ans >= INF) ans = -1;
    cout << ans;
}