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

문제

백준 1504 특정한 최단 경로 C++

1504번: 특정한 최단 경로

풀이

다익스트라를 사용합니다.

정점 v1, v2를 지나고 1부터 시작해서 N에서 끝나는 경로는 다음 2가지 중 하나입니다.

1) 1 -> v1 -> v2 -> N

2) 1 -> v2 -> v1 -> N

따라서 다익스트라를 3번 사용하여 각각의 최소거리를 구해주고 1)과 2)중 최솟값이 정답이 됩니다.

1), 2)의 경로로 모두 도달이 불가능 할 때 (INF일 때)는 -1을 출력합니다.

소스 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int INF = 98765432;
int N, E, v1, v2;
int Dist[801];
vector<pair<int, int>> Vertex[801];
// 다익스트라
void Dijkstra(int Start)
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, Start));
    Dist[Start] = 0;
    while (!PQ.empty())
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
        for (int i = 0; i < Vertex[Cur].size(); i++)
        {
            int Next = Vertex[Cur][i].second;
            int nCost = Vertex[Cur][i].first;
            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
}
// Dist 초기화
void Init() {
    for (int i = 1; i <= N; i++) {
        Dist[i] = INF;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> E;
    int a, b, cost;
    for (int i = 0; i < E; i++) {
        cin >> a >> b >> cost;
        Vertex[a].push_back(make_pair(cost, b));
        Vertex[b].push_back(make_pair(cost, a));
    }
    cin >> v1 >> v2;
    Init();
    Dijkstra(1);
    // 1 to V1, 1 to V2
    int StoV1 = Dist[v1];
    int StoV2 = Dist[v2];
    // V1 to V2, V1 to N
    Init();
    Dijkstra(v1);
    int V1toV2 = Dist[v2];
    int V1toN = Dist[N];
    // v2 to N
    Init();
    Dijkstra(v2);
    int V2toN = Dist[N];
    // S V1 V2 E와 S V2 V1 E 비교
    int ans = min(StoV1 + V1toV2 + V2toN, StoV2 + V1toV2 + V1toN);
    if (ans >= INF) {
        cout << -1;
    }
    else {
        cout << ans;
    }
    return 0;
}