裸的分层图最短路，直接做就好了，问题是手动循环队列的那个地方要加上，不然RE到爽。。而且注意加上了以后改变一下队列的存储顺序。。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m,k,s,tt; const int N=2e5+5; const int inf=2147483646; int head[N],next[N],go[N],val[N]; int dis[N][13]; bool vis[N][13]; int q[N][11],tot; inline void spfa() { memset(dis,127/3,sizeof(dis)); int t=0,w=1; q[0][0]=s,q[0][1]=0; vis[s][0]=1; dis[s][0]=0; while (t!=w) { int x=q[t][0],tmp=q[t++][1]; if (t==100001)t=0; for(int i=head[x];i;i=next[i]) { int v=go[i]; if (dis[x][tmp]+val[i]<dis[v][tmp]) { dis[v][tmp]=dis[x][tmp]+val[i]; if (!vis[v][tmp]) { vis[v][tmp]=1; q[w][0]=v,q[w++][1]=tmp; if (w==100001)w=0; } } if (dis[x][tmp]<dis[v][tmp+1]&&tmp<k) { dis[v][tmp+1]=dis[x][tmp]; if (!vis[v][tmp+1]) { vis[v][tmp+1]=1; q[w][0]=v,q[w++][1]=tmp+1; if (w==100001)w=0; } } } vis[x][tmp]=0; } int ans=inf; fo(i,0,k)ans=min(ans,dis[tt][i]); printf("%d\n",ans); } inline void add(int x,int y,int z) { go[++tot]=y; val[tot]=z; next[tot]=head[x]; head[x]=tot; } int main() { scanf("%d%d%d",&n,&m,&k); scanf("%d%d",&s,&tt); fo(i,1,m) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } spfa(); return 0; }