[백준/BOJ] 백준 10217번 : KCM Travel

www.acmicpc.net/problem/10217

10217번: KCM Travel

다익스트라 알고리즘을 이용하였는데, result[위치][비용] = 최소 소요시간을 저장하였고, 우선순위 큐에는 ((-소요시간, 비용), 위치)를 저장해서 문제를 풀었다. 다익스트라 알고리즘 중간에 해당 지역에서 비용이 M을 초과했다면 그 경로는 더 이상 탐색하지 않았다.

 

코드

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

int T;
int N, M, K;
vector<pair<pair<int, int>, int>> adj[101]; //소요시간, 비용, 도착지 순으로 저장

void Pre()
{
	for (int i = 0; i < 101; i++)
		adj[i].clear();
}

int Solve(int start)
{
	vector<vector<int>> result(N + 1, vector<int>(M + 1, 987654321)); //result[위치][비용] = 소요시간
	priority_queue<pair<pair<int, int>, int>> pq; //-소요시간, 비용, 위치

	result[start][0] = 0;
	pq.push(make_pair(make_pair(-0, 0), start));

	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_d = -pq.top().first.first;
		int here_c = pq.top().first.second;
		pq.pop();

		if (here_c > M) //M원을 넘었을때
			continue;

		if (here_d > result[here][here_c])
			continue;

		if (here == N) //목적지일때
			return here_d;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_d = adj[here][i].first.first + here_d;
			int there_c = adj[here][i].first.second + here_c;

			if (there_c <= M)
			{
				if (result[there][there_c] > there_d)
				{
					result[there][there_c] = there_d;
					pq.push(make_pair(make_pair(-there_d, there_c), there));
				}
			}
		}
	}

	return 987654321;
}

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

	cin >> T;

	for (int tc = 0; tc < T; tc++)
	{
		Pre();
		cin >> N >> M >> K;
		for (int i = 0; i < K; i++)
		{
			int u, v, c, d;
			cin >> u >> v >> c >> d;

			adj[u].push_back(make_pair(make_pair(d, c), v));
		}

		int result = Solve(1);

		if (result == 987654321)
			cout << "Poor KCM" << "\n";
		else
			cout << result << "\n";
	}

	return 0;
}