[Baekjoon] 1504. 특정한 최단 경로

문제 링크

주어진 2개의 정점들을 경유하면서 1번 정점에서 N번 정점까지의 최단 경로의 길이를 출력하는 문제이다.
이를 위해 시작점부터 경유지들까지의 거리와, 경유지들부터 N번 정점까지의 거리를 각각 구하여 더 짧은 거리를 출력하는 방식으로 풀었다.

즉, 1번 정점부터 경유지1까지의 거리 + 경유지1부터 경유지2까지의 거리 + 경유지2에서 N번 정점까지의 거리와 1번 정점부터 경유지2까지의 거리 + 경유지 2부터 경유지1까지의 거리 + 경유지1에서 N번 정점까지의 거리를 비교하는 것이다.
만약 두 값이 모두 INF값이라면 -1을 출력한다.

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

#define INF 987654321

using namespace std;

int N, E;

int x1, x2;
vector<pair<int, int>> myGraph[805];

int dijkstra(int start, int dest)
{
    priority_queue<pair<int, int>> pq;
    vector<int> dist(805, INF);

    dist[start] = 0;
    pq.push(make_pair(0, start));

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

        if (cost > dist[cur])
            continue;

        for (int i = 0; i < myGraph[cur].size(); i++)
        {
            int next = myGraph[cur][i].first;
            int ncost = cost + myGraph[cur][i].second;

            if (ncost < dist[next])
            {
                dist[next] = ncost;
                pq.push(make_pair(-ncost, next));
            }
        }
    }

    return dist[dest];
}

int main()
{
    cin >> N >> E;

    for (int i = 0; i < E; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;

        myGraph[x].push_back(make_pair(y, c));
        myGraph[y].push_back(make_pair(x, c));
    }

    cin >> x1 >> x2;

    int starttox1 = dijkstra(1, x1);
    int x1tox2 = dijkstra(x1, x2);
    int x2todest = dijkstra(x2, N);
    int starttox2 = dijkstra(1, x2);
    int x1todest = dijkstra(x1, N);

    long long int answer1 = starttox1 + x1tox2 + x2todest;
    long long int answer2 = starttox2 + x1todest + x1tox2;

    long long int answer = answer1 < answer2 ? answer1 : answer2;

    if (answer >= INF || answer <= 0)
        cout << -1;
    else
        cout << answer << endl;

    return 0;
}