[골4] 1504 - 특정한 최단 경로

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

using IntPair = pair<int, int>;

#define y first
#define x second

vector<IntPair> adj[805];
int d[805];
priority_queue<IntPair, vector<IntPair>, greater<IntPair>> pq;
const int MAX = 4e8;
int N, E;

void Dijk(int start) 
{
    fill(d, d + N + 2, MAX);
    d[start] = 0;
    
    //첫 번째 길이, 두 번째 정점
    pq.push({ d[start],start });

    while (!pq.empty()) 
    {
        auto cur = pq.top(); pq.pop();

        if (d[cur.x] != cur.y) 
            continue;

        for (auto nxt : adj[cur.x]) 
        {
            if (d[nxt.x] > d[cur.x] + nxt.y) 
            {
                d[nxt.x] = d[cur.x] + nxt.y;
                pq.push({ d[nxt.x],nxt.x });
            }
        }
    }
}

int main() 
{
    //무방향성
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> E;

    for (int i = 0; i < E; i++) 
    {
        int from, to, dist;
        cin >> from >> to >> dist;
        adj[from].push_back({ dist,to });
        adj[to].push_back({ dist,from });
    }
    int v1, v2;
    cin >> v1 >> v2;

    Dijk(1); //1 ->v1, 1->v2 가능
    int onetov1 = d[v1];
    int onetov2 = d[v2];

    Dijk(v1); //v1 -> v2 또는 v1 -> N
    int v1tov2 = d[v2];
    int v1toN = d[N];

    Dijk(v2); //v2 -> v1 또는 v2 -> N
    int v2toN = d[N];
    int v2tov1 = d[v1];

    int sum1 = onetov1 + v1tov2 + v2toN;
    int sum2 = onetov2 + v2tov1 + v1toN;

    int answer = min(sum1, sum2);

    if (answer >= MAX) 
        cout << -1;

    else 
        cout << answer;

    return 0;
}