[백준] 10217 - KCM Travel

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

10217번: KCM Travel

 

기존 다익스트라에서 최대로 갈 수 있는 가중치 정보와 그때 필요한 소요시간이 추가된 문제이다.

따라서 가중치가 2개(비용, 시간)라 볼 수 있다.

 

핵심은 비용이 최소로 되는 경로를 선택해도 시간이 최소가 아닐 수 있다는 것이다.

그래서 dp를 사용하게 되었다.

 

dp[i][j] = i번  정점을 탐색하고, j만큼의 비용이 들었을 때 최소로 걸리는 시간

으로 배열을 정의하였다.

 

이렇게만 하면 금방 풀리는데, 시간이 아슬아슬하게 통과된다.

이것을 최적화까지 해보겠다.

 

먼저 문제 구현부를 살펴보자.

기존 다익스트라에서 비용과 시간을 이용해 추가로 조건이 붙어야 한다.

 

while (!q.empty()) {
	int now = q.top().second.first;
	int cost = -q.top().first;
	int Time = q.top().second.second;
	q.pop();

	if (dp[now][cost] < Time || cost > m) continue;

	for (auto& i : info[now]) {
		int nxNode = i.first;
		int nxCost = i.second.first + cost;
		int nxTime = i.second.second + Time;

		if (nxCost > m) continue;
		if (dp[nxNode][nxCost] <= nxTime)continue;
		dp[nxNode][nxCost] = nxTime;
		q.push({ -nxCost,{nxNode,nxTime } });
	}
}

 

위 부분은 nxNode를 방문할 때 nxCost를 가지고 방문할 수 있는 최단 시간을 갱신하는 다익스트라 부분이다.

이 소스로 채점을 돌렸을 때 6588ms가 나왔다.

 

첫 번째로 적용했던 최적화는 답을 찾았을 때 바로 빠져나오는 것이었다.

즉 q.pop() 바로 밑 부분에 아래와 같은 코드를 추가하였다.

 

if (now == n) {
	cout << Time << '\n';
	ok = 1;
	break;
}

 

우선순위 큐를 이용했으므로 도착지점에 도달했을 때 항상 최솟값을 갖게 된다.

이 부분까지 적용시켰을 때 3252ms, 반으로 줄었다.

 

하지만 최종적으로 시간을 제일 많이 줄인 최적화는 다음 과정이다.

만약 다음과 같은 상황이 벌어졌다고 생각해보자.

dp[2][10] = 10

..

dp[2][20] = 20

..

dp[2][50] = 25

..

dp[2][100] = 11

 

이런 과정에서 dp[2][20], dp[2][50], dp[2][100]의 값은 모두 10으로 설정해도 무리가 없다.

왜냐하면 더 작은 비용으로 더 적은 시간 내에 도착했으므로 항상 최소이기 때문이다.

따라서 다음과 같은 코드를 추가시켰다.

 

for (int j = nxCost + 1; j <= m; j++) {
	if (dp[nxNode][j] <= nxTime)break;
	dp[nxNode][j] = nxTime;
}

 

변경 값보다 탐색하려는 dp값이 작을 때는 당연히 갱신하면 안 되므로 break문으로 제어를 걸었다.

이 소스로 288ms가 나왔다.

10초 제한 문제를 0.3초까지 줄이려면 이런 테크닉까지 구사해야 한다...

 

아래는 전체 소스이다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int n, m, k;
		cin >> n >> m >> k;
		vector<vector<pair<pair<int, int>, int>>> info(n + 1);
		vector<vector<int>> dp(n + 1, vector<int>(m + 1, 987654321));
		for (int i = 0; i < k; i++) {
			int u, v, c, d;
			cin >> u >> v >> c >> d;
			info[u].push_back({ {c,d},v });
		}
		priority_queue<pair<pair<int, int>, int>> q;
		q.push({ {0,0},1 });
		dp[1][0] = 0;
		int ok = 0;
		while (!q.empty()) {
			int now = q.top().second;
			int cost = -q.top().first.second;
			int Time = -q.top().first.first;
			q.pop();

			if (dp[now][cost] < Time || cost > m) continue;
			if (now == n) {
				cout << Time << '\n';
				ok = 1;
				break;
			}

			for (auto& i : info[now]) {
				int nxNode = i.second;
				int nxCost = i.first.first + cost;
				int nxTime = i.first.second + Time;

				if (nxCost > m) continue;
				if (dp[nxNode][nxCost] <= nxTime)continue;

				for (int j = nxCost + 1; j <= m; j++) {
					if (dp[nxNode][j] <= nxTime)break;
					dp[nxNode][j] = nxTime;
				}

				dp[nxNode][nxCost] = nxTime;
				q.push({ {-nxTime,-nxCost},nxNode });
			}
		}
		if (!ok)cout << "Poor KCM\n";
	}
}