题意：给你一张图，有s和t，然后有k次免费的机会，问你最小花费是多少
思路：之前其实网络赛考过一道这样的题，其实就是原题，记得那次被spfa卡死了，后来也没太看分层图，今天补下
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=1200100; const int maxm=1200100; int cnt; struct node { int from,to,val,next; }edge[maxm<<1]; int head[maxm]; LL dis[maxn]; int vis[maxn]; struct Node { int val,id; bool operator <(const Node &b)const { if(val==b.val)return id<b.id; return val>b.val; } }; void init() { memset(head,-1,sizeof(head)); cnt=1; } void addedge(int from,int to,int val) { edge[cnt].from=from; edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } void dijkstra(int s,int e) { memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis)); Node now; priority_queue<Node>q; while(q.size())q.pop(); now.val=0,now.id=s; dis[s]=0; q.push(now); while(!q.empty()){ Node u=q.top(); q.pop(); if(vis[u.id])continue; vis[u.id]=1; for(int i=head[u.id];i!=-1;i=edge[i].next){ int to=edge[i].to; if(dis[u.id]+edge[i].val<dis[to]){ dis[to]=dis[u.id]+edge[i].val; Node pus; pus.id=to,pus.val=dis[to]; q.push(pus); } } } return ; } int main() { int n=read(),m=read(),k=read(); int s=read(),t=read(); s++;t++; init(); for(int i=1;i<=m;i++){ int u=read(),v=read(),w=read(); u++;v++; for(int j=0;j<=k;j++){ addedge(j*n+u,j*n+v,w); addedge(j*n+v,j*n+u,w); if(j!=k){ addedge(j*n+u,(j+1)*n+v,0); addedge(j*n+v,(j+1)*n+u,0); } } } dijkstra(s,t); LL ans=0x3f3f3f3f3f3f3f3fLL; for(int i=0;i<=k;i++){ ans=min(ans,dis[i*n+t]); } printf("%lld ",ans); return 0; }