[BOJ/Gold 1] 백준 10776 제국(C++)

문제 링크

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

10776번: 제국

 

문제

사회에 불만이 많은 지용이는 미적분학 교과서를 적당히 찢어서, 한 사람이 충분히 탈 만한 두께 K의 뗏목을 만들었다.

지용이는 이제 A 항구에서 출발해서 무인도 B에 자신의 제국을 건설하기 위해 멀고 먼 여행을 떠날 계획이다. (1 ≤ A, B ≤ N, A ≠ B)

바다에는 N개의 섬이 있고 M개의 바닷길이 있으며, 바닷길 외의 길로는 갈 수가 없으며 지용이는 A에서 B로 가는 동안 섬들을 거쳐가면서 항해할 계획이다.

각 바닷길은 지나가는 데 걸리는 시간 ti, 뗏목을 깎아내리는 정도 hi (cm) 를 가지고 있으며, 만약에 도착하기 전에 뗏목이 0cm 이하의 두께를 가지게 된다면 - 달리 말해서 경로 상의 hi의 합이 K 이상이 된다면, 수영을 못하는 지용이의 목숨을 보장하지 못할수도 있다(!)

지용이는 가장 빠른 시간 내에 A에서 B 지점까지 안전하게 가기를 원한다. 지용이를 도와 그러한 길의 길이를 출력해주자.

입력

첫 번째 줄에는 정수 K, N, M (1 ≤ K ≤ 200; 2 ≤ N ≤ 2000; 1 ≤ M ≤ 10000)이 주어진다.

이 후 M개의 줄에 각 바닷길의 정보가 A, B, ti, hi (1 ≤ A,B ≤ N; 1 ≤ ti ≤ 105; 0 ≤ hi ≤ 200) 형태로 주어진다. 이는 A와 B를 잇는 바닷길이 존재하며, 이 바닷길은 ti의 시간이 걸리며 hi 만큼 뗏목을 깎아내린다는 것을 의미한다. A ≠ B임이 보장된다.

마지막 줄에는 시작점과 도착점인 A, B가 주어진다. (1 ≤ A, B ≤ N; A ≠ B)

출력

지용이가 안전하게 A에서 B에서 항해할 수 있다면 그 때 걸리는 시간을, 그럴 수 없다면 -1을 출력한다.

예제 입력 1

10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4

예제 출력 1

7

예제 입력 2

3 3 3
1 2 5 1
3 2 8 2
1 3 1 3
1 3

예제 출력 2

-1

알고리즘 분류

• 최단 거리 알고리즘

풀이

이 문제랑 비슷한 것 같다.

1884번: 고속도로

뗏목의 두께가 Y인 상태로 X 정점에 도달했을 때의 최단 거리를 기록하는 Cost[X][Y]라는 2차원 배열을 선언해주고, A 정점을 시작점으로 하는 다익스트라를 1번 수행한다. 그리고 뗏목의 두께가 1~K일 때의 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_N 2001
#define MAX_K 201
#define LL long long
#define INF 1e9

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

struct COMP {
	bool operator()(INFO A, INFO B) {
		return (A.Dist > B.Dist);
	}
};

int K, N, M, A, B;
vector<INFO> Edge[MAX_N];
int Cost[MAX_N][MAX_K];
int answer = INF;

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

void Dijkstra() {
	priority_queue<INFO, vector<INFO>, COMP> PQ;
	Cost[A][K] = 0;
	PQ.push({ A,0,K });

	while (!PQ.empty()) {
		int CurD = PQ.top().Dist;
		int CurC = PQ.top().Cost;
		int CurX = PQ.top().Dest;
		PQ.pop();

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

		for (int i = 0; i < Edge[CurX].size(); i++) {
			int nextD = Edge[CurX][i].Dist;
			int nextC = Edge[CurX][i].Cost;
			int nextX = Edge[CurX][i].Dest;
			if (CurC <= nextC) {
				continue;
			}
			if (Cost[nextX][CurC - nextC] > CurD + nextD) {
				Cost[nextX][CurC - nextC] = CurD + nextD;
				PQ.push({ nextX, Cost[nextX][CurC - nextC], CurC - nextC });
			}
		}
	};
}

void Find_Answer() {
	for (int i = 1; i <= K; i++) {
		answer = min(answer, Cost[B][i]);
	}
	if (answer == INF) {
		cout << -1 << "\n";
	}
	else {
		cout << answer << "\n";
	}
}

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

	return 0;
}