[BOJ] 1504번 특정한 최단 경로 (C++)

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

1504번: 특정한 최단 경로

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 801
#define INF 987654321
using namespace std;

vector<pair<int, int>> v[MAX];
int d[MAX];
int n, e;
int v1, v2;

void dijkstra(int start){
	for(int i = 0; i <= n; i++) d[i] = INF;
	d[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({0, start});
	
	while(!pq.empty()){
		int cur = pq.top().second;
		int start_to_cur_dis = -pq.top().first;
		pq.pop();
		
		if(d[cur] < start_to_cur_dis) continue;
		
		for(int i = 0; i < v[cur].size(); i++){
			int next = v[cur][i].first;
			int start_to_next_dis = start_to_cur_dis + v[cur][i].second;
			
			if(d[next] > start_to_next_dis){
				d[next] = start_to_next_dis;
				pq.push({-start_to_next_dis, next});
			}
		}
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> e;
    for(int i = 0; i < e; i++){
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    cin >> v1 >> v2;

    dijkstra(1);
    int onetov1 = d[v1];
    int onetov2 = d[v2];
    
    dijkstra(v1);
    int v1tov2 = d[v2];
    int v1ton = d[n];
    
    dijkstra(v2);
    int v2ton = d[n];
    
    int res = INF;
    res = min(res, onetov1 + v1tov2 + v2ton);
    res = min(res, onetov2 + v1tov2 + v1ton);
    
    if(v1tov2 == INF || res == INF) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}

 

1번 정점부터 N번 정점까지 최단 거리로 방문하면서 v1과 v2를 무조건 방문해야 한다.

따라서 아래와 같이 두 가지 경로가 나올 수 있다.

1. 1 -> v1 -> v2 -> N

2. 1 -> v2 -> v1 -> N

 

이를 위해 다익스트라 함수를 총 세 번 실행한다.

1. start가 1 : 1 -> v1과 1 -> v2 구함

2. start가 v1 : v1 -> v2 구함 (양방향이므로 v2 -> v1과 같음)

3. start가 v2 : v2 -> v1과 v2 -> N 구함

 

세 번의 다익스트라 실행으로 각 거리를 모두 구한 후 경로 1과 2 중 더 작은 값을 출력하면 된다.

*) 경로 중 INF를 세 번 더하는 경우 (INF + INF + INF) int 범위를 초과해 overflow가 발생한다. 따라서 미리 v1 -> v2가 INF인지 검사해준다. v1 -> v2가 INF라면 무조건 정답이 없기 때문에 바로 -1을 출력한다.