本人做法是在逐层跑一次最短路，然后将上一层的数据复制下来。

求教 dalao 为什么不能这样 qwq

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e4+5, MAXM = 5e4+5, MAXK = 25;
int n, m, k, head[MAXN];
long long f[MAXN], tmp[MAXN], ans = LONG_LONG_MAX;	//long long!!!
bool vst[MAXN];

struct node{
	int to, wi, nxt;
} edge[MAXM*2];

struct cmp{
	bool operator () (const int &x, const int &y){
		return f[x] > f[y];
	}
};
priority_queue<int, vector<int>, cmp>	pq;

inline void add(int i, int from, int to, int wi){
	edge[i].to = to;
	edge[i].wi = wi;
	edge[i].nxt = head[from];
	head[from] = i;
	return;
}

inline void init(){
	while(!pq.empty())			pq.pop();
	for(int i = 1; i <= n; i++)	vst[i] = false;
	for(int i = 1; i <= n; i++)	tmp[i] = f[i];
	for(int i = 1; i <= n; i++)
		for(int j = head[i]; j; j = edge[j].nxt)
			f[edge[j].to] = min(tmp[i], f[edge[j].to]);
	for(int i = 1; i <= n; i++)
		if(f[i] < tmp[i])	pq.push(i);
	return;
}

inline void dijkstra(){
	while(!pq.empty()){
		int cur = pq.top(); pq.pop();
		if(vst[cur])	continue;
		vst[cur] = true;
		for(int i = head[cur]; i; i = edge[i].nxt){
			int to = edge[i].to;
			if(vst[to])						continue;
			if(f[to] <= f[cur]+edge[i].wi)	continue;
			f[to] = f[cur]+edge[i].wi;
			pq.push(to);
		}
	}
	return;
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m; i++){
		int ui, vi, wi;			scanf("%d%d%d", &ui, &vi, &wi);
		add(i*2-1, ui, vi, wi);	add(i*2, vi, ui, wi);
	}
	for(int i = 1; i <= n; i++)	f[i] = 0x3f3f3f3f3f3f3f3f;
	f[1] = 0;	pq.push(1);
	dijkstra();	ans = f[n];
	for(int i = 1; i <= k; i++){
		init();
		dijkstra();
		ans = min(ans, f[n]);
//		for(int j = 1; j <= n; j++)	cout<<f[j]<<" "; cout<<endl;
	}
	cout<<ans;
	
	return 0;
}