建一个分层图,第\(i\)层的第\(j\)个节点表示走到\(j\)号节点,用了\(i\)个优惠的最短路,我们设为\([i,j]\)。

然后对于原图的一条权值为\(w\)的双向边\((u,v)\),对于任意的\(0\le x\le k\),在\([x,u]\)和\([x,v]\)之间建立权值为\(w\)的双向边,对于任意的\(0\le x<k\),在\([x,u]\)和\([x+1,v]\)之间以及\([x,v]\)和\([x+1,u]\)之间分别建立单向边。

从\([0,s]\)开始跑单源最短路,答案为\(0\le x\le k\)的\([x,t]\)到\([0,s]\)的最短路的最小值。

code:

#include
    
     #define val(u,id) (n*(u)+id)using namespace std;struct node{    int d,mn;    bool operator<(node y)const{        return mn==y.mn?d>y.d:mn>y.mn;    }}td;struct edge{    int t,v,nxt;}e[2200010];const int INF=1e9;int n,m,k,s,t,u,v,w,be[110010],cnt,mn[110010],vis[110010],ans=INF;priority_queue
     
      pq;void add(int x,int y,int val){    e[++cnt].t=y,e[cnt].v=val,e[cnt].nxt=be[x],be[x]=cnt;}void Dijkstra(){    for(int i=0;i<=k;++i)for(int j=0;j
      
       mn[td.d]+e[i].v)?mn[e[i].t]=mn[td.d]+e[i].v,pq.push((node){e[i].t,mn[e[i].t]}),0:0;    }}int main(){    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);    for(int i=1;i<=m;++i){        scanf("%d%d%d",&u,&v,&w);        for(int j=0;j