[BAEKJOON] 10217번 : KCM Travel*

문 제

 

소 스  코 드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>


constexpr int START	{ 0 };
constexpr int INF	{ 1'000'654'321 };

// 비용과 소요시간
struct Airplane {
	int mNext;
	int mCost;
	int mTime;
};

std::vector<std::vector<Airplane>> mEdge;
int mDist[101][10001];


void TravelKCM();
void Dijkstra(const int&, const int&);


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

	int T;
	std::cin >> T;

	for (int i = 0; i < T; ++i) TravelKCM();

	return 0;
}

void TravelKCM() {

	mEdge.clear();

	int N, M, K;
	std::cin >> N >> M >> K;

	mEdge.resize(N + 1);

	int u, v, c, d;
	for (int i = 0; i < K; ++i) {
		std::cin >> u >> v >> c >> d;
		mEdge[u].emplace_back(Airplane{ v, c, d });
	}
	
	Dijkstra(N, M);
}

void Dijkstra(const int& N, const int& M) {

	for (int i = 0; i <= N; ++i) std::fill_n(mDist[i], M + 1, INF);

	
	mDist[1][0] = 0;
	std::priority_queue<std::pair<int, std::pair<int, int>>> pQue;
	pQue.push({ 0, { 0, 1 } });	// cost, time, pos

	while (!pQue.empty()) {
		int h			{ pQue.top().second.second };
		int hTime		{ pQue.top().second.first };	// 우선순위 큐는 오름차순
		int hCost		{ -pQue.top().first };

		pQue.pop();

		if (mDist[h][hCost] < hTime) continue;

		for (const auto& a : mEdge[h]) {
			int n		{ a.mNext };
			int nCost	{ a.mCost + hCost };
			int nTime	{ a.mTime + hTime };

			if (nCost > M) continue;

			if (mDist[n][nCost] > nTime) {
				for (int i = nCost; i <= M; ++i) {
					if (mDist[n][i] > nTime) mDist[n][i] = nTime;
				}
				pQue.push({ -nCost, {nTime, n} });
			}
		}

	}

	int ret{ INF };
	for (int i = 0; i <= M; ++i) ret = std::min(ret, mDist[N][i]);

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

 

풀 이

 

• 문제 풀이 링크

다익스트라 알고리즘 + 다이나믹 플밍을 응용하여 풀 수 있는 문제이다.

다익스트라 알고리즘의 경우에는 하나의 거리 정보만 가지고 문제를 해결하지만,

이 문제는 거리와 제한적인 비용을 통하여 구현을 해야하는 문제이다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : www.acmicpc.net/problem/10217

10217번: KCM Travel