头皮发麻

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int maxn=3e5+10;

int n,m,k,tot,s,t;
int dis[maxn],g[maxn];
bool vis[maxn];
struct line
{
	int to,next,w;
}edge[maxn*20];
struct node
{
	int id,w;
	node(int idd,int ww){id=idd,w=ww;}
};
priority_queue<node>pq;

bool operator<(const node &a,const node &b)
{
	return a.w>b.w;
}
void add1(int a,int b,int c)
{
	edge[++tot].to=b;
	edge[tot].w=c;
	edge[tot].next=g[a];
	g[a]=tot;
}
void dij()
{
	memset(dis,0x3f,sizeof(dis));
	pq.push(node(s,0));
	while(!pq.empty())
	{
		node temp=pq.top();
		pq.pop();
		if(vis[temp.id])continue;
		vis[temp.id]=true;
		dis[temp.id]=temp.w;
		for(int i=g[temp.id];i;i=edge[i].next)
			if(!vis[edge[i].to]&&dis[edge[i].to]>dis[temp.id]+edge[i].w)
			{
				dis[edge[i].to]=dis[temp.id]+edge[i].w;
				pq.push(node(edge[i].to,dis[edge[i].to]));
			}
	}
}

int main()
{
	scanf("%d %d %d",&n,&m,&k);
	scanf("%d %d",&s,&t);
	s++,t++;
	for(int i=1;i<=m;i++)
	{
		int x=0,y=0,z=0;
		scanf("%d %d %d",&x,&y,&z);
		x++,y++;
		for(int j=0;j<=k;j++)
		{
			add1(x+j*n,y+j*n,z);
			add1(y+j*n,x+j*n,z);
			if(j!=k)
			{
				add1(x+j*n,y+(j+1)*n,0);
				add1(y+j*n,x+(j+1)*n,0);
			}
		}
	}
	dij();
	int ans=0x3f3f3f3f;
//	for(int i=1;i<=k;i++)ans=min(ans,dis[t+i*n]);
	cout<<dis[t+k*n];
	return 0;
}