[백준] 골드4 : (1504) 특정한 최단 경로

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

1504번: 특정한 최단 경로

 

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

int N, E, V1, V2, Cnt;
map<int, vector<pair<int, int>>> m;
vector<int> Dist, SaveDist;

void Dijkstra(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({ 0, start });
    Dist[start] = 0;

    while (!pq.empty())
    {
        int c = pq.top().first;
        int n = pq.top().second;
        pq.pop();

        for (const auto& i : m[n])
        {
            if (Dist[i.first] > c + i.second)
            {
                Dist[i.first] = c + i.second;
                pq.push({ Dist[i.first], i.first });
            }
        }
    }
}

void Clear()
{
    Dist.clear();
    Dist.resize(N + 1, 987654321);
}

bool Assert()
{
    if (Cnt >= 987654321)
    {
        Cnt = 987654321;
        return true;
    }
    return false;
}

void Func(int v1, int v2)
{
    Cnt += Dist[v1];
    if (Assert()) return;

    Clear();

    Dijkstra(v1);

    Cnt += Dist[v2];
    if (Assert()) return;

    Clear();

    Dijkstra(v2);

    Cnt += Dist[N];
    if (Assert()) return;
}

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

    cin >> N >> E;

    Dist.resize(N + 1, 987654321);
    for (int i = 0, a, b, c; i < E; ++i)
    {
        cin >> a >> b >> c;
        m[a].push_back({ b, c });
        m[b].push_back({ a, c });
    }

    cin >> V1 >> V2;

    Dijkstra(1);
    SaveDist = Dist;

    Func(V1, V2);
    int save = Cnt;
    Cnt = 0;
    Dist = SaveDist;

    Func(V2, V1);
    if (save == 987654321 && Cnt == 987654321) cout << -1 << "\n";
    else cout << min(save, Cnt) << "\n";
}

1 -> v1 -> v2와 1 -> v2 -> v1 중 최솟값을 출력한다.