用的 Dijkstra，求条，玄关。

#include <cstdio>
#include <functional>
#include <queue>
#include <utility>
std::vector<std::vector<std::pair<int, int>>> to;
std::vector<bool> f;
std::vector<int> nk;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
int n, m, k, s, t, u, v, w;
int main(){
	scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
	nk.resize(k + 1);
	for (int i = 0; i < k; ++i){
		nk[i + 1] = nk[i] + n;
	}
	to.resize(n * k + n);
	f.resize(n * k + n);
	while (m--){
		scanf("%d%d%d", &u, &v, &w);
		for (int i = 0; i < k; ++i){
			to[u + nk[i]].emplace_back(v + nk[i], w);
			to[v + nk[i]].emplace_back(u + nk[i], w);
			to[u + nk[i]].emplace_back(v + nk[i + 1], 0);
			to[v + nk[i]].emplace_back(u + nk[i + 1], 0);
		}
		to[u + nk[k]].emplace_back(v + nk[k], w);
		to[v + nk[k]].emplace_back(u + nk[k], w);
	}
	q.emplace(0, s);
	while (!q.empty()){
		std::pair<int, int> p = q.top();
		q.pop();
		int root = p.second, sp = p.first;
		if (root % n == t){
			printf("%d", sp);
			return 0;
		}
		f[root] = true;
		for (const std::pair<int, int> &pp : to[root]){
			int ch = pp.first;
			if (!f[ch]){
				q.emplace(sp + pp.second, ch);
			}
		}
	}
	return 0;
}