[C++] 백준 10217 : KCM Travel

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

10217번: KCM Travel

백준 10217번 KCM Travel 을 풀었다.

 

특정 노드에서 시작하고 간선의 가중치가 양수이므로 다익스트라를 사용했다.

변수가 비용과 시간 두개이므로 2차원 배열을 사용해서 풀어야 한다.

dp[i][j] 는 시작 노드 1에서 i 노드까지 j 비용을 썼을 때의 소요시간을 저장하는 배열이다.

 

https://maivve.tistory.com/226

위 블로그를 참고해서 코드를 작성했다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#pragma warning(disable:4996)
using namespace std;

#define INF	123456789
struct node {
	int dest;
	int fee;
	int time;
};
struct compare {
	bool operator()(node a, node b) {
		return a.time > b.time;
	}
};

vector<node> vertex[101];
vector<int> dp[101];

void Dijkstra(int n,int m) {
	priority_queue<node, vector<node>, compare> pq;
	for (int i = 0; i <= n; i++) {
		dp[i].assign(m + 1, INF);
	}
	node temp = { 1,0,0 };
	pq.push(temp);


	while (!pq.empty()) {
		int cur = pq.top().dest;
		int fee = pq.top().fee;
		int time = pq.top().time;
		pq.pop();

		if (dp[cur][fee] < time)
			continue;

		for (int i = 0; i < vertex[cur].size(); i++) {
			int next = vertex[cur][i].dest;
			int next_fee = fee + vertex[cur][i].fee;
			int next_time = time + vertex[cur][i].time;

			if (next_fee > m)
				continue;

			if (dp[next][next_fee] > next_time) {

				for (int j = next_fee + 1; j <= m; j++) {
					if (dp[next][j] <= next_time)
						break;
					dp[next][j] = next_time;
				}

				dp[next][next_fee] = next_time;
				pq.push({ next,next_fee,next_time });
			}
		}
	}

	int min = INF;
	for (int i = 1; i <= m; i++) {
		if (min > dp[n][i])
			min = dp[n][i];
	}

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

int main() {
	int tc;
	cin >> tc;
	while (tc--) {
		int n, m, k;
		cin >> n >> m >> k;
		for (int i = 0; i < k; i++) {
			int start, end, fee, time;
			scanf("%d %d %d %d", &start, &end, &fee, &time);
			node temp = { end,fee,time };
			vertex[start].push_back(temp);
		}

		Dijkstra(n, m);

		for (int i = 1; i <= n; i++)
			vertex[i].clear();

	}
}