传送门：https://www.luogu.org/problem/P4568
跑个分层图。
有人说数组开小了，RE了，说实话我很蒙蔽。直接用d[i][j]表示到i已用了j条免费通道不就行了吗？
#include<cstdio> #include<queue> #include<algorithm> #include<cstring> #define R register using namespace std; int n,m,k,s,t,tot,head[11000],ver[100100],nex[100100],cost[100100]; inline void add(int x,int y,int z){ ver[++tot]=y;nex[tot]=head[x];cost[tot]=z;head[x]=tot; } int d[11000][20]; bool v[11000]; queue<int> q; inline void work(int cn){ q.push(s);d[s][cn]=0; while(q.size()){ int x=q.front();q.pop();v[x]=0; for(R int i=head[x];i;i=nex[i]){ if(d[ver[i]][cn]>d[x][cn]+cost[i]){ d[ver[i]][cn]=d[x][cn]+cost[i]; if(!v[ver[i]]) q.push(ver[i]); } if(d[ver[i]][cn]>d[x][cn-1]){ d[ver[i]][cn]=d[x][cn-1]; if(!v[ver[i]]) q.push(ver[i]); } } } } int main (){ scanf("%d%d%d",&n,&m,&k); scanf("%d%d",&s,&t); s++;t++; for(R int x,y,z,i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); x++;y++; add(x,y,z);add(y,x,z); } memset(d,0x3f,sizeof(d)); d[s][0]=0;q.push(s);v[s]=1; while(q.size()){ int x=q.front();q.pop();v[x]=0; for(R int i=head[x];i;i=nex[i]){ if(d[ver[i]][0]>d[x][0]+cost[i]){ d[ver[i]][0]=d[x][0]+cost[i]; if(!v[ver[i]]) q.push(ver[i]); } } } for(R int i=1;i<=k;i++) work(i); printf("%d ",d[t][k]); return 0; }