[BOJ] 23793번 두 단계 최단 경로 1 (C++)

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

23793번: 두 단계 최단 경로 1

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 2e9
#define MAX 100001
#define MAX_EDGE 200001
using namespace std;

int n, m, x, y, z;
int d[MAX];
vector<pair<int, int>> v[MAX_EDGE];

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].second;
			int start_to_next_dis = start_to_cur_dis + v[cur][i].first;
			
			if(d[next] > start_to_next_dis){
				d[next] = start_to_next_dis;
				pq.push({-start_to_next_dis, next});
			}
		}
	}
}

void dijkstra2(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].second;
			int start_to_next_dis = start_to_cur_dis + v[cur][i].first;
			
			if(next == y) continue;
			
			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 >> m;
	
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({c, b});
	}
	
	cin >> x >> y >> z;
	
	dijkstra(x);
	int t = d[y];
	dijkstra(y);
	if(t == INF || d[z] == INF) cout << -1 << " ";
	else cout << t + d[z] << " ";

	dijkstra2(x);
	if(d[z] == INF) cout << -1 << endl;
	else cout << d[z] << endl;
	return 0;
}

 

1. Y를 거쳐가는 경우(dijkstra)

(x → y 최단거리) + (y → z 최단거리)로 나눌 수 있다. x를 시작점으로 dijkstra를 돌려서 나오는 d[y]값, y를 시작점으로  dijkstra를 돌려서 나오는 d[z]값을 더한다.

 

2. Y를 거치지 않는 경우(dijkstra2)

next가 y일 경우 해당 간선 추가 작업을 수행하지 않고 넘어가도록 한다.

 

 

*) 처음에 INF를 987654321로 설정하여 틀렸는데 2e9로 바꾼 뒤 AC를 받았다.