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

문제 링크

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

23801번: 두 단계 최단 경로 2

문제

서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으로 갖고 도시 간의 도로를 간선으로 갖는 무방향성 그래프이며(undirected graph), 도로의 길이가 간선의 가중치이다. 출발 정점 X에서 출발해서 P개의 중간 정점 중 적어도 한 개의 정점을 반드시 거친 후 도착 정점 Z에 도달하는 최단 거리를 구해서 우리 서준이를 도와주자.

입력

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

다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타낸다. (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w ≤ 1,000,000)

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

다음 줄에 P가 주어진다. (1 ≤ P ≤ N - 3)

다음 줄에 P개의 서로 다른 중간 정점 Y (1 ≤ Y ≤ N, X ≠ Y ≠ Z)가 빈칸을 사이에 두고 주어진다.

출력

출발 정점 X에서 출발해서 P개의 중간 정점 중 적어도 한 개의 정점을 반드시 거친 후 도착 정점 Z에 도달하는 최단 거리를 출력한다. 도착 정점 Z에 도착할 수 없는 경우 -1을 출력한다.

예제 입력 1

13 19
1 2 100
1 3 100
1 4 1
2 5 1
3 6 1
3 4 1
4 6 1
4 7 1
5 6 10
5 8 10
6 9 10
7 10 1
8 9 10
8 11 1
9 11 1
9 12 1
10 12 2
11 13 1
12 13 3
1 13
3
8 9 10

예제 출력 1

8

1번 - 4번 - 7번 - 10번 - 12번 - 13번 순서로 방문 하는 게 최단 거리이다.

예제 입력 2

13 19
1 2 1
1 3 2
1 4 10
2 5 1
3 6 10
3 4 10
4 6 1
4 7 1
5 6 10
5 8 1
6 9 1
7 10 1
8 9 1
8 11 100
9 11 100
9 12 100
10 12 1
11 13 100
12 13 1
1 13
3
8 9 10

예제 출력 2

10

1번 - 2번 - 5번 - 8번 - 9번 - 6번 - 4번 - 7번 - 10번 - 12번 - 13번 순서로 방문 하는 게 최단 거리이다.

알고리즘 분류

• 최단 거리 알고리즘

풀이

X에서 출발하는 경우, Z에서 출발하는 경우 이렇게 2번의 다익스트라를 실행한다.

그리고 X->Y 최단 거리 + Y->Z 최단 거리의 최솟값을 구한다.

코드

#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 1e11

using namespace std;
int N, M, X, Z, P;
vector<pair<int, LL> > Edge[MAX];
LL Cost[2][MAX];
LL answer = INF * 2;

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

void Dijkstra(int I, int S) {
	priority_queue<pair<LL, int> > PQ;
	Cost[I][S] = 0;
	PQ.push(make_pair(0, S));

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

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

		for (int i = 0; i < Edge[CurX].size(); i++) {
			LL 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 Find_Answer() {
	cin >> P;
	for (int i = 0; i < P; i++) {
		int Y;
		cin >> Y;
		if ((Cost[0][Y] != INF) && (Cost[1][Y] != INF)) {
			answer = min(answer, Cost[0][Y] + Cost[1][Y]);
		}
	}
	if (answer != INF * 2) {
		cout << answer << "\n";
	}
	else {
		cout << -1 << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Dijkstra(0, X);
	Dijkstra(1, Z);
	Find_Answer();

	return 0;
}