(C++) - 백준(BOJ) 1504번 : 특정한 최단 경로

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

다익스트라 문제였습니다.

 

풀이방법

 시작정점을 a, 거쳐야할 두 정점을 각각 v1,v2 도착정점을 b라고 가정했을때 가는 최단경로가 있다면 다음과 같이 두 가지 경로가 있습니다.

 1) a -> v1 -> v2 -> b

 2) a -> v2 -> v1 -> b

1), 2)중 최소인 경로를 출력, 경로가 없다면 -1을 출력해주면 됩니다.

 

1. 1)의 답은 a -> v1으로 가는 최단경로 + v1 -> v2로 가는 최단경로 + v2 -> b로 가는 최단경로입니다. 다익스트라 3번으로 구할 수 있습니다. 2)도 마찬가지로 구합니다.

 

2. 정답을 출력합니다. 경로의 합이 무한대라면 경로가 없다는 뜻이므로 -1을 출력해줍니다.

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
using pii = pair<int,int>;
int n, e, v1, v2, d[801];
vector <pii> graph[801];

int dijkstra(int start, int end){
    priority_queue <pii, vector<pii>, greater<pii>> pq;
    pq.push({0,start});
    d[start] = 0;
    while(!pq.empty()){
        int curCost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if(d[cur] < curCost) continue;
        for(auto &el : graph[cur]){
            int next = el.first;
            int nextCost = el.second;
            if(curCost + nextCost < d[next]){
                d[next] = curCost + nextCost;
                pq.push({d[next],next});
            }
        }
    }
    return d[end];
}

int main(){
    cin >> n >> e;

    while(e--){
        int u,v,w;
        cin >> u >> v >> w;
        graph[u].push_back({v,w});
        graph[v].push_back({u,w});
    }

    cin >> v1 >> v2;
    memset(d,INF,sizeof(d));
    ll aToV1 = dijkstra(1, v1);

    memset(d,INF,sizeof(d));
    ll v1ToV2 = dijkstra(v1,v2);
    
    memset(d,INF,sizeof(d));
    ll v2Tob = dijkstra(v2,n);

    memset(d,INF,sizeof(d));
    ll aToV2 = dijkstra(1, v2);

    memset(d,INF,sizeof(d));
    ll v2ToV1 = dijkstra(v2,v1);

    memset(d,INF,sizeof(d));
    ll v1Tob = dijkstra(v1,n);

    ll ans = aToV1 + v1ToV2 + v2Tob;
    ll ans2 = aToV2 + v2ToV1 + v1Tob;

    if(ans >= INF && ans >= INF) cout << -1;
    else cout << min(ans,ans2);
}