这道题有55分都是最短路板子。但是我们肯定不满足于55分，看了题解才知道这道题是一个叫分层图最短路的东西。
对于k次免费机会，相当于建了k层图，每一层的图都是原图上的边权，但是每一层之间所连的边权为0，并且是有向边，我的理解是，因为我们只有一次机会，没有反悔？洛谷上的大佬说的是因为这样才满足dag的性质。
代码如下，其实还是很好理解的：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int n,m,k,s,t,x,y,v; struct node{ int nxt,to,val; }edge[maxn*3]; int head[maxn],cnt; void add(int x,int y,int v){ edge[++cnt].nxt=head[x]; edge[cnt].to=y; edge[cnt].val=v; head[x]=cnt; } priority_queue<pair<int,int> >q; int vis[maxn]; long long ans; bool can[1550][1550]; long long dis[maxn]; void dijkstra(int x){ memset(dis,88,sizeof(dis)); memset(vis,false,sizeof(vis)); dis[x]=0; q.push(make_pair(0,x)); while(q.size()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=true; for(int i=head[u];i;i=edge[i].nxt){ int go=edge[i].to; if(dis[go]>dis[u]+edge[i].val){ dis[go]=dis[u]+edge[i].val; q.push(make_pair(-dis[go],go)); } } } } int main(){ scanf("%d%d%d",&n,&m,&k); scanf("%d%d",&s,&t); s++,t++; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&v); x++,y++; add(x,y,v);add(y,x,v); for(int j=1;j<=k;j++){ add(x+(j*n),y+(j*n),v); add(y+(j*n),x+(j*n),v); add(x+(j-1)*n,y+(j*n),0); add(y+(j-1)*n,x+(j*n),0); } } for(int i=1;i<=k;i++) add(t+(i-1)*n,t+(i*n),0); dijkstra(s); printf("%d\n",dis[t+k*n]); return 0; }
推荐几道分层图的模板题：