同。

注意本题起点终点不是\(s,t\)而是\(1,n\),之前在不同层之间建立的权值为\(0\)的边权值改为\(w/2\)即可。

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[210010];const int INF=1e9;int n,m,k,u,v,w,be[2600],cnt,mn[2600],vis[2600],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=1;j<=n;++j)mn[val(i,j)]=INF;    mn[1]=0,pq.push((node){1,0});    while(!pq.empty()){        while(!pq.empty()&&vis[(td=pq.top(),td.d)])pq.pop();        if(pq.empty())return;        pq.pop(),vis[td.d]=1;        for(int i=be[td.d];i;i=e[i].nxt)(mn[e[i].t]>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",&n,&m,&k);    for(int i=1;i<=m;++i){        scanf("%d%d%d",&u,&v,&w);        for(int j=0;j