[BOJ/Gold 2] 백준 23033 집에 빨리 가고 싶어!(C++)

문제 링크

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

23033번: 집에 빨리 가고 싶어!

 

문제

가톨릭대학교에 다니는 쿠기는 수업을 마치고 집에 가려고 한다.

쿠기는 지하철을 이용하여 집에 가려고 하는데, 쿠기가 사는 도시의 지하철은 매우 복잡해서 학교에서 집까지 갈 수 있는 가장 빠른 경로의 소요 시간을 알기가 힘들다. 쿠기는 집에 혼자 있는 강아지가 걱정되어 집에 빨리 가고 싶다. 걱정하는 쿠기를 도와 집으로 가는 가장 빠른 경로를 찾아 최단 시간을 알려주자.

쿠기가 탈 지하철 노선도에 포함된 역은 N개가 있으며, 각 역은 1~N까지의 번호로 구분한다. 가톨릭대학교 앞 역인 역곡역은 1번이고, 쿠기가 내릴 역은 N번 역이다.

쿠기가 타는 지하철에는 M개의 노선이 있다. 각 노선은 출발역과 도착역으로만 이루어져 있다. 쿠기는 최단 경로를 계산하기 위해 각각의 노선의 출발역과 도착역, 출발역에서 도착역까지 걸리는 시간과 다음 열차와의 간격이 적혀있는 정보를 얻었다. A역(1 ≤ A ≤ N)에서 B역(1 ≤ B ≤ N, A ≠ B)으로 출발하는 노선은 여러 개가 존재할 수 있으며, A역에서 출발하여 B역에 도착하는 데 걸리는 시간은 T(1 ≤ T ≤ 10)시간이다. 모든 열차는 12시에 각 노선의 출발역에서 운행을 시작하며, W(1 ≤ W ≤ 10)시간마다 같은 노선에서 새로운 열차가 출발한다. 단, 각 역에서 지하철을 갈아타는 데에는 시간이 걸리지 않는다.

쿠기는 모든 열차가 운행을 시작하는 시점에 1번 역에서 승차한다. 쿠키가 N번 역에 도착하는데 걸리는 최단 시간을 구하시오.

입력

첫째 줄에 역의 수 N(2 ≤ N ≤ 20,000)과 노선 M개(1 ≤ M ≤ 300,000)가 주어진다. 둘째 줄 부터 M개의 줄에 걸쳐서 4개의 정수 A, B, T, W가 주어지고 A역에서 B역으로 가는 단방향 노선이 존재하며, 소요되는 시간은 T(1 ≤ T ≤ 10)이고, 열차는 W(1 ≤ W ≤ 10)의 시간마다 출발한다는 뜻이다.(N번 역으로 항상 도착할수 있다)

출력

1번 역에서 12시에 출발하여 N번 역으로 가는 최단 시간을 출력한다.

예제 입력 1

5 7
1 2 1 2
1 3 2 1
2 3 3 4
2 4 2 2
2 5 6 3
3 5 1 6
4 5 1 4

예제 출력 1

5

알고리즘 분류

• 최단 거리 알고리즘

풀이

1번 역을 시작점으로 하는 다익스트라를 수행한다.

이 때, A번 역에서 B번 역으로 갈 때 열차가 존재한다면 이동하고, 열차가 없다면 열차가 올 때까지 기다린다.

코드

#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 20001
#define LL long long
#define INF 1e11

using namespace std;
struct INFO {
	LL Dest, Cost, W;
};

int N, M;
vector<INFO> Edge[MAX];
LL Cost[MAX];

void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		Cost[i] = INF;
	}
	for (int i = 0; i < M; i++) {
		int A, B, T, W;
		cin >> A >> B >> T >> W;
		Edge[A].push_back({ B,T,W });
	}
}

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

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

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

		for (int i = 0; i < Edge[CurX].size(); i++) {
			LL nextCost = Edge[CurX][i].Cost;
			LL nextX = Edge[CurX][i].Dest;
			LL nextW = Edge[CurX][i].W;
			if (CurCost % nextW == 0) {
				if (Cost[nextX] > CurCost + nextCost) {
					Cost[nextX] = CurCost + nextCost;
					PQ.push(make_pair(-Cost[nextX], nextX));
				}
			}
			else {
				LL R = 0;
				for (LL j = 0; j < 10; j++) {
					if ((CurCost + j) % nextW == 0) {
						R = CurCost + j;
						break;
					}
				}
				if (Cost[nextX] > nextCost + R) {
					Cost[nextX] = nextCost + R;
					PQ.push(make_pair(-Cost[nextX], nextX));
				}
			}
		}
	};
}

void Find_Answer() {
	cout << Cost[N] << "\n";
}

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

	return 0;
}