[C/C++] 백준 10217번 - KCM Travel (다익스트라)

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<tuple>
using namespace std;

typedef tuple<int, int, int> TUPLE;

#define INF 1000000000

int T, N, M, K;
int u, v, c, d;
int dp[101][10001], ans;
vector<TUPLE> graph[101];

void init() // 초기화
{
	for (int i = 1; i <= 100; i++)
	{
		graph[i].clear();

		for (int j = 0; j <= 10000; j++)
			dp[i][j] = INF;
	}
	ans = INF;
}

void dijkstra()
{
	priority_queue<TUPLE, vector<TUPLE>, greater<TUPLE>> pq;

	dp[1][0] = 0;
	pq.push({ 0, 1, 0 }); // 누적 시간, 출발지, 누적 비용 

	while (!pq.empty())
	{
		int time = get<0>(pq.top()); // 누적 시간
		int now = get<1>(pq.top()); // 현재 공항
		int money = get<2>(pq.top()); // 누적 비용
		
		pq.pop();

		if (dp[now][money] < time) continue;

		for (int i = 0; i < graph[now].size(); i++) // i : 목적지
		{
			int next_time = time + get<0>(graph[now][i]); // 소요 시간
			int next = get<1>(graph[now][i]); // 다음 공항
			int next_money = money + get<2>(graph[now][i]); // 소요 비용
			

			// 지원 비용으로 갈 수 없을 경우 pass
			if (next_money > M) continue;

			// 해당 공항에 해당 비용으로 갈때의 최소 시간보다 크다면 pass
			if (dp[next][next_money] <= next_time) continue;

			// 해당 공항에 최소시간으로 가는 비용보다 높은 비용으로 가는 방법들을
			// 최소시간으로 업데이트 해준다 (무의미한 계산을 막기 위함)
			for (int j = next_money; j <= M; j++) {
				if (dp[next][j] > next_time) {
					dp[next][j] = next_time;
				}
			}
			pq.push({ next_time, next, next_money });
		}

	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie();

	cin >> T;

	while (T--)
	{
		init();

		cin >> N >> M >> K;

		for (int i = 0; i < K; i++)
		{
			cin >> u >> v >> c >> d;
			graph[u].push_back({ d,v,c }); // 시간, 도착지, 비용
		}

		dijkstra();

		for (int i = 1; i <= M; i++) 
			ans = min(ans, dp[N][i]);

		if (ans == INF) cout << "Poor KCM" << '\n';
		else cout << ans << '\n';

	}
}

 

풀이 방법

 

<dp 정의>

dp[i][j] : j 비용으로 i 공항까지 가는 최소 시간

 

굳이 우선순위 큐를 사용하지 않고 큐를 사용해도 코드가 통과된다.

이 문제는 다익스트라로 풀이를 할 수 있는데 문제에서 중요한 점은
해당 공항에 최소 시간으로 갈 수 있는 비용보다 높은 비용이 드는 경로들을 모두 최소시간으로 업데이트해주는 것이다.

for (int j = next_money; j <= M; j++) {
	if (dp[next][j] > next_time) {
		dp[next][j] = next_time;
	}
}

위의 코드를 적어줄 시 무의미한 계산들을 없애줄 수 있고 이러한 코드가 없을 시 아래와 같이 메모리 사용 차이가 난다.

 

 

 

 

 

www.acmicpc.net/problem/10217

10217번: KCM Travel