分层图SPFA
最后必须依次比较，因为可能因为边数太少用不到k次
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,k,S,T,en,h[10005],D[15][10005],flag[15][10005],ans;
struct Que{
int a,b;
Que(int sa,int sb){a=sa;b=sb;}
};
queue<Que> Q;
struct Edge{
int b,v,next;
}e[100005];
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
void SPFA(){
memset(D,127,sizeof(D));
D[0][S]=0;
flag[0][S]=1;
Q.push(Que(0,S));
while(!Q.empty()){
Que u=Q.front();
Q.pop();
flag[u.a][u.b]=0;
for(int i=h[u.b];i;i=e[i].next){
int v=e[i].b;
if(D[u.a][v]>D[u.a][u.b]+e[i].v){
D[u.a][v]=D[u.a][u.b]+e[i].v;
if(!flag[u.a][v]){
flag[u.a][v]=1;
Q.push(Que(u.a,v));
}
}
}
if(u.a<k){
for(int i=h[u.b];i;i=e[i].next){
int v=e[i].b;
if(D[u.a+1][v]>D[u.a][u.b]){
D[u.a+1][v]=D[u.a][u.b];
if(!flag[u.a+1][v]){
flag[u.a+1][v]=1;
Q.push(Que(u.a+1,v));
}
}
}
}
}
ans=D[0][T];
for(int i=1;i<=k;i++){ans=min(ans,D[i][T]);}
}
int main(){
freopen("2763.in","r",stdin);
freopen("2763.out","w",stdout);
scanf("%d %d %d %d %d",&n,&m,&k,&S,&T);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
AddEdge(u,v,w);
AddEdge(v,u,w);
}
SPFA();
printf("%d\n",ans);
return 0;
}
评论 (0)
