C++[백준]10217번 KCM Travel

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

10217번: KCM Travel

 

솔루션

---

이전에 도로포장을 풀고 이번 문제를 풀어서 그런가, 접근 법은 역시나 똑같다.

 

2차원 배열을 선언하는데 [걸린 비용][공항] = 시간 으로 값을 채워주면 풀린다.

 

(풀이법은 도로 포장을 풀어보자.)

 

 

 

코드

---

#define INF 2100000000
#include <iostream>
#include <vector>
#include<queue>
using namespace std;

struct edge {
	int dest, cost, t;
};
struct pa {
	int cost, time, dest;
	
	bool operator<(const struct pa& t) const {
		if (cost == t.cost) {
			if (time == t.time) {
				return dest > t.dest;
			}
			return time > t.time;
		}
		return cost > t.cost;
	}
};

vector<struct edge> V[102];

int value[10002][102];
int N, M, K;


void dijkstra(void) {
	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			value[j][i] = INF;
		}
	}

	priority_queue<struct pa> pq;
	pq.push({ 0,0,1 });

	while (!pq.empty()) {
		int c = pq.top().cost;
		int t = pq.top().time;
		int str = pq.top().dest;
		pq.pop();

		if (value[c][str] < t) continue;

		for (int i = 0; i < V[str].size(); i++) {
			int next = V[str][i].dest;
			int time = V[str][i].t + t;
			int cost = V[str][i].cost + c;

			if (cost > K || value[cost][next] <= time) continue;
			pq.push({ cost,time, next });
			value[cost][next] = time;
		}
	}
	int minValue = INF;
	for (int i = 0; i <= K; i++) {
		minValue = min(minValue, value[i][N]);
	}

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

	for (int i = 0; i <= N; i++) {
		V[i].clear();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int tc;
	cin >> tc;
	while (tc--) {
		cin >> N >> K >> M;

		for (int i = 0; i < M; i++) {
			int str, dest, c, d;
			cin >> str >> dest >> c >> d;
			V[str].push_back({ dest,c,d });
		}

		dijkstra();
		
	}
}