题目链接
这个题就是分层思想的板子题，简而言之，分层思想就是通过状态转移的方式进行维数上的转移
盗一张@EternalAlexander 的图方便理解（样例）
这里只有一个免费限制，所以是一个两层的三维图。
// luogu-judger-enable-o2
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 1000100
#define inf 0x7f
using namespace std;
int dis[maxn];
int n,m,k,s,t;
int head[maxn],vis[maxn],tot;
struct edge
{int u,v,w;int next;
}e[maxn<<1];
void add(int u,int v,int w)
{e[++tot]=(edge){u,v,w,head[u]};head[u]=tot;
}
struct node
{int s,val;bool operator < (node a) const{return a.val<val;}
};
priority_queue<node> q;
void dijkstra(int x)
{memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));dis[x]=0;q.push((node){x,dis[x]});while(!q.empty()){int nowpoint=q.top().s;q.pop();if(vis[nowpoint]) continue;vis[nowpoint]=1;for(int i=head[nowpoint];i;i=e[i].next){int topoint=e[i].v;if(dis[nowpoint]+e[i].w<dis[topoint]){dis[topoint]=dis[nowpoint]+e[i].w;q.push((node){topoint,dis[topoint]});}}}
}
int main()
{ios::sync_with_stdio(false);cin>>n>>m>>k>>s>>t;int u,v,w;for(int i=1;i<=m;i++){cin>>u>>v>>w;add(u,v,w);add(v,u,w);for(int j=1;j<=k;j++){add(u+(j-1)*n,v+j*n,0);add(v+(j-1)*n,u+j*n,0);add(u+j*n,v+j*n,w);add(v+j*n,u+j*n,w);}}dijkstra(s);cout<<dis[t+k*n];
}