[백준 1162] 도로포장

다채롭게도 틀렸내 ㅋ

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

1162번: 도로포장

#include <cstdio>
#include <queue>
#include <list>
int N, M, K;
struct _lt
{
	int node;
	long long int cost;
};

std::list<_lt> L[10000 + 2];

struct _qt
{
	long long int node;
	long long int wrap;
	long long int cost;
};

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

std::priority_queue<_qt, std::vector<_qt>, COMP> PQ;
long long int chk[10000 + 2][20 + 2];		// 특정 n노드까지 가는데 몇개의 도로를 포장했는가


void debug()
{
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			printf("%3d", chk[i][j]);
		}
		printf("\n");
	}
}



void init()
{
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			chk[i][j] = 0x7fffffffffffffff;		// long long type이라서 최대값도 신경써야 한다...
												// 무지성으로 21억 때리면 안됨, 더 커야됨
		}
	}
}


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

long long int BFS()
{
	init();
	
	PQ.push({ 1, 0, 0});
	chk[1][0] = 0;

	while (!PQ.empty()) {
		_qt data = PQ.top();
		PQ.pop();
		
        // 우선순위 큐에서 데이터 꺼내는 조건을 cost가 작을수록, 포장한 도로 수가 적을수록 
        // 우선순위가 높게 지정해주었다.
		if (data.node == N) return data.cost;	

		// PQ 상태 발전 시키기 전에 현 상태와 비교하여 발전시킬 필요가 있는지 따져주어야 한다. 
		// 이거 원래 했었나.. ? // 원래는 안해줌, 근데 타임아웃 나면 고려해볼 필요 있다.
		if (chk[data.node][data.wrap] < data.cost) continue;	

		for (_lt next : L[data.node]) {
			long long int nnode = next.node;
			long long int ncost = data.cost + next.cost;
			//printf("%d %d %d\n", nnode, data.wrap, ncost);
			if (chk[nnode][data.wrap] <= ncost) continue;

			if (data.wrap + 1 <= K) {
				if (chk[nnode][data.wrap + 1] > data.cost) {
					PQ.push({ nnode, data.wrap + 1, data.cost });	// 도로포장함, data.node -> nnode : cost = 0
					chk[nnode][data.wrap + 1] = data.cost;
				}
			}
			PQ.push({ nnode, data.wrap, ncost });
			chk[nnode][data.wrap] = ncost;
		}
	}
}



int main()
{
	input();
	long long int ans = BFS();
	//debug();
	printf("%lld\n", ans);
	return 0;
}