题目

record

code:

#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,t,lon,d[2000001],ans=INT_MAX;
bool flag[2000001];
struct node{
	int r,lon;
};
struct edge{
	int num,whe;
}dui[2000001];
vector<node>a[2000001];
void push(int x,int y){
	lon++;
	dui[lon].num=x;
	dui[lon].whe=y;
	int fa=lon/2,so=lon;
	while(fa){
		if(dui[fa].num>dui[so].num){
			int dt=dui[fa].num;
			dui[fa].num=dui[so].num;
			dui[so].num=dt;
			dt=dui[fa].whe;
			dui[fa].whe=dui[so].whe;
			dui[so].whe=dt;
		}
		else break;
		so=fa;
		fa/=2;
	}
}
void pop(int x){
	dui[x]=dui[lon];
	lon--;
	int fa=x,so=x*2;
	while(so<=lon){
		if(so+1<=lon&&dui[so+1].num<dui[so].num)so++;
		if(dui[so].num<dui[fa].num){
			int dt=dui[fa].num;
			dui[fa].num=dui[so].num;
			dui[so].num=dt;
			dt=dui[fa].whe;
			dui[fa].whe=dui[so].whe;
			dui[so].whe=dt;
		}
		else break;
		fa=so;
		so*=2;
	}
}
int main(){
	cin>>n>>m>>k>>s>>t;
	for(int s0,t0,lon0,i=1;i<=m;i++){
		cin>>s0>>t0>>lon0;
		a[s0].push_back({t0,lon0});
		a[t0].push_back({s0,lon0});
	}
	for(int q=0;q<k;q++){
		for(int i=0;i<n;i++){
			int dt=a[i].size();
			for(int j=0;j<dt;j++){
				a[i+(q+1)*n].push_back({a[i][j].r+(q+1)*n,a[i][j].lon});
				a[a[i][j].r+(q+1)*n].push_back({i+(q+1)*n,a[i][j].lon});
				a[i+q*n].push_back({a[i][j].r+(q+1)*n,0});
//				cout<<i+q*n<<" "<<a[i][j].r+(q+1)*n<<" "<<a[i].size()<<endl;
				//原点： i
				//边:    a[i][j]
				//上一点:i+q*n
				//现点:  i+(q+1)*n
				/////////////////////
				//先建一张图
				//再通过边连一条边权为0的边
			}	
//			cout<<endl;		
		}
//		cout<<endl;
	}
	for(int i=0;i<=(k+1)*n;i++)d[i]=1e10;
	d[s]=0;
	push(0,s);
	while(lon){
		int head=dui[1].whe;
		pop(1);
		if(flag[head])continue;
		flag[head]=1;
		for(int i=0;i<a[head].size();i++){
			if(!flag[a[head][i].r]&&d[a[head][i].r]>d[head]+a[head][i].lon){
				d[a[head][i].r]=d[head]+a[head][i].lon;
				push(d[a[head][i].r],a[head][i].r);
			}
		}
	}
//	for(int i=0;i<(k+1)*n;i++)
//		cout<<d[i]<<" ";
	for(int i=1;i<=k+1;i++)
		ans=min(ans,d[t+(i-1)*n]);
	cout<<ans<<endl;
	return 0;
}