分层spfa。
退队的时候vis=false。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxv 10050 #define maxe 100500 using namespace std; struct edge { int v,w,nxt; }e[maxe]; int n,m,k,s,t,a,b,c,dis[maxv][13],g[maxv],nume=0,vis[maxv][13]; queue <int> q; void addedge(int u,int v,int w) { e[++nume].v=v; e[nume].w=w; e[nume].nxt=g[u]; g[u]=nume; } void spfa() { while (!q.empty()) q.pop(); memset(dis,0x7f,sizeof(dis)); q.push(s);q.push(0);vis[s][0]=true;dis[s][0]=0; while (!q.empty()) { int dot,now; dot=q.front();q.pop(); now=q.front();q.pop(); vis[dot][now]=false; for (int i=g[dot];i;i=e[i].nxt) { int v=e[i].v; if (dis[v][now]>dis[dot][now]+e[i].w) { dis[v][now]=dis[dot][now]+e[i].w; if (!vis[v][now]) { q.push(v); q.push(now); vis[v][now]=true; } } if ((now!=k) && (dis[v][now+1]>dis[dot][now])) { dis[v][now+1]=dis[dot][now]; if (!vis[v][now+1]) { q.push(v); q.push(now+1); vis[v][now+1]=true; } } } } } 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",&a,&b,&c); addedge(a+1,b+1,c); addedge(b+1,a+1,c); } spfa(); int ans=0x7f7f7f7f; for (int i=0;i<=k;i++) ans=min(ans,dis[t][i]); printf("%d ",ans); return 0; }