[BOJ/Gold 3] 백준 23807 두 단계 최단 경로 3(C++)

문제 링크

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

23807번: 두 단계 최단 경로 3

 

문제

서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으로 갖고 도시 간의 도로를 간선으로 갖는 무방향성 그래프이며(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가 주어진다. (3 ≤ P ≤ min(100, N - 3))

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

출력

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

예제 입력 1

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

예제 출력 1

8

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

알고리즘 분류

• 최단 거리 알고리즘

풀이

우선 X를 시작점으로 하는 다익스트라를 실행한다. 그리고 입력받은 P개의 점 각각을 시작점으로 하는 다익스트라를 실행한다. 따라서, 다익스트라를 최대 101번 실행하게 된다.

그리고, 최대 100개의 점 중 3개, A, B, C를 골라서 X->A 최단 거리, A->B 최단 거리, B->C 최단 거리, C->Z 최단 거리의 합을 구한다. 최대 100P3개의 합 중 최솟값이 답이 된다.

코드

#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_N 100001
#define MAX_P 101
#define LL long long
#define INF 1e11

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

void Init() {
	for (int i = 0; i < MAX_P; i++) {
		for (int j = 1; j <= N; j++) {
			Cost[i][j] = INF;
		}
	}
}

void Input() {
	cin >> N >> M;
	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));
	}
	Init();
	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 Settings() {
	Dijkstra(0, X);
	cin >> P;
	for (int i = 1; i <= P; i++) {
		int Y;
		cin >> Y;
		CheckPoint.push_back(Y);
		Dijkstra(i, Y);
	}
}

void Find_Answer() {
	for (int i = 0; i < CheckPoint.size(); i++) {
		for (int j = 0; j < CheckPoint.size(); j++) {
			for (int k = 0; k < CheckPoint.size(); k++) {
				if ((i == j) || (j == k) || (i == k)) {
					continue;
				}
				if ((Cost[0][CheckPoint[i]] != INF) && (Cost[i + 1][CheckPoint[j]] != INF) && (Cost[j + 1][CheckPoint[k]] != INF) && (Cost[k + 1][Z] != INF)) {
					answer = min(answer, Cost[0][CheckPoint[i]] + Cost[i + 1][CheckPoint[j]] + Cost[j + 1][CheckPoint[k]] + Cost[k + 1][Z]);
				}
			}
		}
	}
	if (answer != INF * 5) {
		cout << answer << "\n";
	}
	else {
		cout << -1 << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}