[BOJ/Gold 2] 백준 2982 국왕의 방문(C++)

문제 링크

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

2982번: 국왕의 방문

 

문제

지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안에 다른 차량이 들어올 수 없게 통제할 것이다. 하지만, 그가 진입하기 전부터 길에 있던 차량은 계속 있을 수 있다.

상근이는 오토바이 소년 승환이의 뒤를 이어 근처에서 피자를 트럭으로 배달하는 사람이다. 상근이는 교통 통제 때문에 배달을 정시에 하지 못해서 짤릴뻔했다.

이미 고둘라 창지즈 영사우드는 상그니 아라비아로 돌아갔다. 하지만 상근이는 고둘라가 한국에 왔었을 때, 어떤 길로 이동을 했어야 배달을 빠르게 할 수 있었는지 알아보려고 한다. 상근이는 고둘라가 이동한 경로를 알고 있다.

도시는 여러 개의 교차로와 교차로를 서로 연결하는 양방향 도로로 모델링할 수 있다. 상근이는 각 도로를 이동하는데 걸리는 시간을 알고 있다. 고둘라가 그 도로를 이동하는데 걸리는 시간도 같다.

예를 들어, 고둘라가 10분이 되던 때에 어떤 도로에 도착했고, 그 도로를 통과하는데 걸리는 시간이 5라고 하자. 그럼 이 도로는 10, 11, 12, 13, 14분에는 진입할 수 없다. 상근이는 9분 이전, 15분 이후에 이 도로에 진입할 수 있다.

상근이가 배달을 하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오. 상근이는 고둘라가 출발하고 K분이 지난 후에 배달을 시작한다.

입력

첫째 줄에 교차로의 수 N과 도로의 수 M이 주어진다. 교차로는 1번부터 N번까지 번호가 매겨져 있다. (2 ≤ N ≤ 1000, 2 ≤ M ≤ 10,000)

둘째 줄에는 네 정수 A, B, K, G가 주어진다. (1 ≤ A, B ≤ N, 0 ≤ K ≤ 1000, 0 ≤ G ≤ 1000) A는 상근이가 배달을 시작하는 교차로, B는 상근이가 배달을 마치는 교차로이다. K는 고둘라가 출발한 시간과 상근이가 출발한 시간의 차이, G는 고둘라가 방문하는 교차로의 개수이다.

셋째 줄에는 G개의 정수가 주어진다.이 정수는 고둘라가 방문하는 교차로이다. 인접한 교차로 사이의 거리를 고둘라가 이동하는 것이다. 항상 도로는 존재하며, 각 도로를 최대 한 번만 이동한다.

넷째 줄부터 M개 줄에는 도로의 정보를 나타내는 세 정수 U, V, L이 주어진다. 교차로 U와 V를 연결하는 도로를 이동하는데 L분이 걸린다는 뜻이다. L은 1보다 크거나 같고, 1000보다 작거나 같은 정수이다.

출력

첫째 줄에 상근이가 배달을 마치는데 필요한 가장 빠른 시간을 출력한다.

예제 입력 1

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

예제 출력 1

21

예제 입력 2

8 9
1 5 5 5
1 2 3 4 5
1 2 8
2 7 4
2 3 10
6 7 40
3 6 5
6 8 3
4 8 4
4 5 5
3 4 23

예제 출력 2

40

알고리즘 분류

• 최단 거리 알고리즘

풀이

주어진 정보를 입력받고, 어떤 도로가 몇 분부터 몇 분까지 지나갈 수 없는 지를 기록한다.

그리고 다익스트라를 실행하면서, 현재 시각에 해당 도로를 지나갈 수 없으면 도로의 봉쇄가 풀린 후에 지나가도록 하고, 해당 도로를 지나갈 수 있으면 그냥 지나가면 된다.

도로의 봉쇄 정보를 기록하는 데 시간이 좀 걸리지만 다익스트라는 한 번만 실행하기 때문에 시간 제한에 걸리지 않는다.

코드

#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 1001
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int Dest, Cost, S, E;
};

int N, M, A, B, K, G;
vector<INFO> Edge[MAX];
int Cost[MAX];
int visit_Node[MAX];
int visited_Time = 0;
int answer = 0;

void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		Cost[i] = INF;
	}
	cin >> A >> B >> K >> G;
	for (int i = 1; i <= G; i++) {
		cin >> visit_Node[i];
	}
	for (int i = 0; i < M; i++) {
		int U, V, L;
		cin >> U >> V >> L;
		Edge[U].push_back({ V,L,-1,-1 });
		Edge[V].push_back({ U,L,-1,-1 });
	}
	for (int i = 1; i < G; i++) {
		int S = visit_Node[i];
		int E = visit_Node[i + 1];
		bool Flag = false;
		for (int j = 1; j <= N; j++) {
			for (int k = 0; k < Edge[j].size(); k++) {
				if (((j == S) && (Edge[j][k].Dest == E)) || ((j == E) && (Edge[j][k].Dest == S))) {
					Edge[j][k].S = visited_Time;
					Edge[j][k].E = visited_Time + Edge[j][k].Cost - 1;
					if (!Flag) {
						Flag = true;
					}
					else {
						visited_Time += Edge[j][k].Cost;
					}
				}
			}
		}
	}
}

void Dijkstra() {
	priority_queue<pair<int, int> > PQ;
	Cost[A] = K;
	PQ.push(make_pair(-K, A));

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

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

		for (int i = 0; i < Edge[CurX].size(); i++) {
			int nextCost = Edge[CurX][i].Cost;
			int nextX = Edge[CurX][i].Dest;
			if ((CurCost >= Edge[CurX][i].S) && (CurCost <= Edge[CurX][i].E)) {
				int Tmp = Edge[CurX][i].E + 1;
				if (Cost[nextX] > Tmp + nextCost) {
					Cost[nextX] = Tmp + nextCost;
					PQ.push(make_pair(-Cost[nextX], nextX));
				}
			}
			else {
				if (Cost[nextX] > CurCost + nextCost) {
					Cost[nextX] = CurCost + nextCost;
					PQ.push(make_pair(-Cost[nextX], nextX));
				}
			}
		}
	};
}

void Find_Answer() {
	cout << Cost[B] - Cost[A] << "\n";
}

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

	return 0;
}