[BOJ] 1162 : 도로포장

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int n_ = 10000 + 1;

struct edg {
	int idx, dst, cnt;
	edg() {}
	edg(int idx, int dst) : idx(idx), dst(dst) {}
	edg(int idx, int dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {}
	bool operator <(edg A)const { return dst > A.dst; }
};

int n, m, k;
int dst[n_][21];
vector<edg> gph[n_];

void dijkstra() {
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= k; ++j) dst[i][j] = 987654321;
	dst[1][k] = 0;

	priority_queue<edg> pq;
	pq.push(edg(1, 0, k));

	while (!pq.empty()) {
		edg now = pq.top();
		pq.pop();

		if (now.dst != dst[now.idx][now.cnt]) continue;

		for (auto nxt : gph[now.idx]) {
			if (dst[nxt.idx][now.cnt] > now.dst + nxt.dst) {
				dst[nxt.idx][now.cnt] = now.dst + nxt.dst;
				pq.push(edg(nxt.idx, dst[nxt.idx][now.cnt], now.cnt));
			}
			if (now.cnt > 0) {
				if (dst[nxt.idx][now.cnt - 1] > now.dst) {
					dst[nxt.idx][now.cnt - 1] = now.dst;
					pq.push(edg(nxt.idx, now.dst, now.cnt - 1));
				}
			}
		}
	}
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 0; i < m; ++i) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		gph[x].push_back(edg(y, z));
		gph[y].push_back(edg(x, z));
	}

	dijkstra();

	int ans = 999999999;
	for (int i = 0; i <= k; ++i) ans = min(ans, dst[n][i]);

	printf("%d", ans);

	return 0;
}