题解

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e4 + 10, M = 5e4 + 10;
int n, m, k, s, t;
struct node {
	int v, w;//终点，权值
    friend bool operator<(node a, node b){
		return a.w > b.w;
	}
};
vector<node> v[12 * M];

int dis[12 * N];
int vis[12 * N];
priority_queue<node> pq;

void dij() {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	pq.push({ s,0 });

	while (!pq.empty()) {
		node t = pq.top();
		pq.pop();

		if (vis[t.v]) continue;
		vis[t.v] = 1;

		for (auto i : v[t.v]) {
			int v = i.v;
			int w = i.w;
			if (!vis[v]) {
				if (dis[v] > dis[t.v] + w) {
					dis[v] = dis[t.v] + w;
					pq.push({ v,dis[v] });
				}
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;
	cin >> s >> t;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		for (int j = 0; j <= k; j++) {
			//本层的图
			v[a + j * n].push_back({ b + j * n,c });
			v[b + j * n].push_back({ a + j * n,c });

			//本层和下层的图
			if (j != k) {
				v[a + j * n].push_back({ b + (j + 1) * n,0 });
				v[b + j * n].push_back({ a + (j + 1) * n,0 });
			}
		}
	}

	dij();

	int ans = 0x3f3f3f3f;
	for (int i = 0; i <= k; i++) {
		ans = min(ans, dis[t + i * n]);
	}
	cout << ans;
	return 0;
}