[BOJ/Gold 4] 백준 23793 두 단계 최단 경로 1(C++)

문제 링크

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

23793번: 두 단계 최단 경로 1

 

문제

서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으로 갖고 도시 간의 도로를 간선으로 갖는 방향성 그래프이며(directed graph), 도로의 길이가 간선의 가중치이다. 도시의 번호는 1부터 N까지이다. 출발 정점 X에서 출발하여 중간 정점 Y를 거쳐서 도착 정점 Z에 도달하는 최단 거리, 출발 정점 X에서 출발하여 중간 정점 Y를 거치지 않고 도착 정점 Z에 도달하는 최단 거리를 각각 구해서 우리 서준이를 도와주자.

입력

첫째 줄에 정점의 수 N (1 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000)이 주어진다.

다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u에서 도시 v로 가중치가 w인 단방향 도로를 나타낸다. (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w ≤ 10,000, w는 정수) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

다음 줄에 X Y Z가 주어진다. (1 ≤ X, Y, Z ≤ N, X ≠ Y, X ≠ Z, Y ≠ Z)

출력

첫째 줄에 두 정수를 출력한다. 첫 번째 정수는 정점 X에서 출발해서 정점 Y를 거쳐서 정점 Z에 도달하는 최단 거리를 의미한다. 두 번째 정수는 정점 X에서 출발해서 정점 Y를 거치지 않고 정점 Z에 도달하는 최단 거리를 의미한다.

만약, 정점 Z에 도달할 수 없는 경우 -1을 출력한다.

예제 입력 1

6 8
1 2 2
1 3 3
1 5 10
2 4 3
3 6 5
4 1 4
4 6 4
5 6 1
1 2 6

예제 출력 1

9 8

정점의 개수 N은 6이고 간선의 개수 M은 8이다. 출발 정점 1에서 중간 정점 2를 거쳐 도착 정점 6에 도달 하는 최단 경로는 정점 1 2 4 6 순으로 방문하면 된다. 출발 정점 1에서 중간 정점 2를 거치지 않고 도착 정점 6에 도달하는 최단 경로는 정점 1 3 6순으로 방문하면 된다.

예제 입력 2

6 8
1 2 2
1 3 3
1 5 10
2 4 3
3 6 5
4 1 4
4 6 4
5 6 1
1 2 4

예제 출력 2

5 -1

알고리즘 분류

• 최단 거리 알고리즘

풀이

주어진 정보를 입력받고, X->Y, Y->Z, X->Z(Y를 안 거치는 경우) 세 가지의 다익스트라를 실행해서 최단 거리를 구해준다. 첫 번째는 X->Y 최단 거리 + Y->Z 최단 거리를 출력하며, 두 번째는 X->Z(Y를 안 거치는 경우) 최단 거리를 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int N, M, X, Y, Z;
vector<pair<int, int> > Edge[MAX];
int Cost[3][MAX];

void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		Cost[0][i] = INF;
		Cost[1][i] = INF;
		Cost[2][i] = INF;
	}
	for (int i = 0; i < M; i++) {
		int U, V, W;
		cin >> U >> V >> W;
		Edge[U].push_back(make_pair(V, W));
	}
	cin >> X >> Y >> Z;
}

void Dijkstra1(int I, int S, int E) { // 정점 X에서 출발해서 정점 Y를 거치는 경우
	priority_queue<pair<int, int> > PQ;
	Cost[I][S] = 0;
	PQ.push(make_pair(0, S));

	while (!PQ.empty()) {
		int CurCost = -PQ.top().first;
		int CurX = PQ.top().second;
		PQ.pop();

		if (CurX == E) {
			return;
		}

		if (Cost[I][CurX] < CurCost) {
			continue;
		}

		for (int i = 0; i < Edge[CurX].size(); i++) {
			int nextCost = Edge[CurX][i].second;
			int nextX = Edge[CurX][i].first;
			if (Cost[I][nextX] > CurCost + nextCost) {
				Cost[I][nextX] = CurCost + nextCost;
				PQ.push(make_pair(-Cost[I][nextX], nextX));
			}
		}
	};
}

void Dijkstra2() { // 정점 X에서 출발해서 정점 Y를 거치지 않는 경우
	priority_queue<pair<int, int> > PQ;
	Cost[2][X] = 0;
	PQ.push(make_pair(0, X));

	while (!PQ.empty()) {
		int CurCost = -PQ.top().first;
		int CurX = PQ.top().second;
		PQ.pop();

		if (Cost[2][CurX] < CurCost) {
			continue;
		}

		for (int i = 0; i < Edge[CurX].size(); i++) {
			int nextCost = Edge[CurX][i].second;
			int nextX = Edge[CurX][i].first;
			if (nextX == Y) {
				continue;
			}
			if (Cost[2][nextX] > CurCost + nextCost) {
				Cost[2][nextX] = CurCost + nextCost;
				PQ.push(make_pair(-Cost[2][nextX], nextX));
			}
		}
	};
}

void Find_Answer() {
	if ((Cost[0][Y] != INF) && (Cost[1][Z] != INF)) {
		cout << Cost[0][Y] + Cost[1][Z] << " ";
	}
	else {
		cout << -1 << " ";
	}
	if (Cost[2][Z] != INF) {
		cout << Cost[2][Z] << " ";
	}
	else {
		cout << -1 << " ";
	}
	cout << "\n";
}

int main() {
	FASTIO
	Input();
	Dijkstra1(0, X, Y);
	Dijkstra1(1, Y, Z);
	Dijkstra2();
	Find_Answer();

	return 0;
}