[백준 10217] KCM Travel

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

10217번: KCM Travel

#include <cstdio>
#include <queue>
#include <list>
using namespace std;
int T;
int N, M, K;
int visited[100 + 2][10000 + 2];	// 1 -> i, 총비용 j, 소요시간 visited[i][j]

struct _st
{
	int arp;
	int cost;
	int time;
};

std::list<_st> L[100 + 2];	

struct COMP
{
	bool operator()(_st &a, _st &b)
	{
		if (a.time == b.time) return a.cost > b.cost;
		return a.time > b.time;
	}
};


priority_queue<_st, vector<_st>, COMP> PQ;



void init()
{
	N = M = K = 0;
	for (int i = 1; i <= 101; i++) {
		L[i].clear();
		for (int j = 0; j < 10001; j++) {
			visited[i][j] = 0x7fffffff;
		}
	}
	PQ = {};
}


void input()
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < K; i++) {
		int u = 0, v = 0, c = 0, d = 0;
		scanf("%d %d %d %d", &u, &v, &c, &d);
		L[u].push_back({ v, c, d });
	}
}


int BFS()
{
	visited[1][0] = 0;		// 인천 -> 인천, 총 0원 사용, 0시간 소요
	PQ.push({ 1, 0, 0 });	// 인천arp, 총 0원 사용, 0시간 소요

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.arp == N) return visited[N][data.cost];

		for (_st next : L[data.arp]) {
			int narp = next.arp;
			int ncost = data.cost + next.cost;
			int ntime = visited[data.arp][data.cost] + next.time;

			if (ncost > M) continue;
			if (visited[narp][ncost] <= ntime) continue;
			//printf("n: %d c: %d  t: %d\n", narp, ncost, ntime);
			visited[narp][ncost] = ntime;
			PQ.push({ narp, ncost, ntime });
		}
	}
	return -1;
}


int main()
{
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		init();
		input();
		int ans = BFS();
		if (ans == -1) printf("Poor KCM\n");
		else printf("%d\n", ans);

	}
	return 0;
}

 

소요시간 뿐 만 아니라 해당 공항에 도착하는데 필요한 총 비용까지 고려해야 된다.

비용이 M 이하이기만 하면 되는줄 알고 방문 배열 일차원으로 만들고 소요시간만 따져주다가 두 번 틀림..... 아니 비용 고려하라는 소리 어디있냐고.. 

 

기존 코드는 큐 썼다가, 그냥 FIFO로는 어떻게 비용까지 따져주어야 할지 막막해서 (ncost전 까지 for문 돌려야하나.. 했음 ㅋ) 우선순위 큐로 다시 구현했다. 

일단 소요시간이 짧으면 우선적으로 pop하고, 소요시간이 같을 경우에는 총 비용이 작은 공항을 pop하도록 COMP 함수를 생성했다.