문제 푼 날짜 : 2021-07-07

문제

문제 링크 : https://www.acmicpc.net/problem/1504

접근 및 풀이

1번 정점에서 N번 정점까지 도달하는 최단거리에 v1과 v2를 반드시 거쳐야하므로 두 가지의 경로를 고려해줘야한다.

1. 1 -> v1 -> v2 -> N
2. 1 -> v2 -> v1 -> N

일반적인 다익스트라 알고리즘을 적용하여 1번, v1, v2에서 각각 출발한 값들을 찾고 두 가지 케이스에 맞게 거리계산을 해주었다.
이 두 경로의 거리를 구했을 때 값이 더 작은 경로를 출력해주었다.

코드

// 백준 1504번 : 특정한 최단 경로
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF 987654321

int N, E;
vector<pair<int, int>> v[801];

vector<int> dijkstra(int start) {
    vector<int> dist(N + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[start] = 0;
    pq.push({ 0, start });

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

        if (dist[now] < cost) {
            continue;
        }
        for (int i = 0; i < v[now].size(); i++) {
            int next = v[now][i].first;
            int nCost = v[now][i].second + cost;

            if (nCost < dist[next]) {
                dist[next] = nCost;
                pq.push({ nCost, next });
            }
        }
    }
    return dist;
}

int main() {
    int ans = 0;
    cin >> N >> E;

    while (E--) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b, c });
        v[b].push_back({ a, c });
    }
    int v1, v2;
    cin >> v1 >> v2;

    vector<int> temp1 = dijkstra(1); // 1에서 출발
    vector<int> temp2 = dijkstra(v1); // v1에서 출발
    vector<int> temp3 = dijkstra(v2); // v2에서 출발
    
    // 1 -> v1 -> v2 -> N 과 1 -> v2 -> v1 -> N 중 최소값
    ans = min(temp1[v1] + temp2[v2] + temp3[N], temp1[v2] + temp3[v1] + temp2[N]); 

    if (ans >= INF || ans < 0) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }
    return 0;
}

결과

피드백

다익스트라 기본 알고리즘 구현은 어느정도 익숙해진듯 하다.