[C++/백준] 1504번: 특정한 최단 경로

문제 링크

1504번: 특정한 최단 경로

 

풀이

다익스트라로 푸는 최단 경로 문제.
1 -> u -> v -> n과 1 -> v -> u -> n을 비교하면 되는 문제

1. 입력 받으며 인접리스트를 만든다.
2. 위에서 설명한 루트대로 다익스트라로 최단 경로를 구한다.
   1. 다익스트라는 거리 벡터를 모두 무한대로 초기화 하고 현재 시작할 노드를 0으로 만들고 현재 노드부터 우선순위 큐에 넣어 시작한다.
   2. dist의 값이 최소로 갱신될 때마다 pq에 노드를 넣어준다.
   3. 그렇게 while문이 끝나면 dist에 현재 노드부터 각 노드까지 최소 거리가 만들어질 것이다.
   4. 도착 노드를 return
3. 그렇게 두 개의 루트의 값을 구해 최솟값으로 출력해주는데, 이 값이 무한대보다 크거나 같다면 -1을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#define INF 200000001
using namespace std;

int func(int u, int v, int n, vector<vector<pair<int,int>>> &adj)
{
    vector<int> dist(n + 1, INF);
    priority_queue<pair<int, int>> pq;

    dist[u] = 0;
    pq.push({ 0, u });

    while (!pq.empty())
    {
        int cur = pq.top().second;
        pq.pop();
        for (int i = 0; i < adj[cur].size(); i++)
        {
            int next = adj[cur][i].second;
            int cost = adj[cur][i].first;
            if (dist[next] > dist[cur] + cost)
            {
                dist[next] = dist[cur] + cost;
                pq.push({ cost, next });
            }
        }
    }

    return dist[v];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, e;
    cin >> n >> e;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < e; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({ c,b });
        adj[b].push_back({ c,a });
    }
    int u, v;
    cin >> u >> v;

    int n1 = func(1, u, n, adj);
    int n2 = func(u, v, n, adj);
    int n3 = func(v, n, n, adj);
    int n4 = func(1, v, n, adj);
    int n5 = func(u, n, n, adj);

    int answer = min(n1 + n2 + n3, n4 + n2 + n5);

    if (answer >= INF)
    {
        cout << -1;
    }
    else
    {
        cout << answer;
    }
}