水题可以愉悦身心
分层图SPFA
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,k,en,h[55],D[55][55],flag[55][55],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[2005];
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));
flag[0][1]=1;
D[0][1]=0;
Q.push(Que(0,1));
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]+e[i].v/2){
D[u.a+1][v]=D[u.a][u.b]+e[i].v/2;
if(!flag[u.a+1][v]){
flag[u.a+1][v]=1;
Q.push(Que(u.a+1,v));
}
}
}
}
}
ans=D[0][n];
for(int i=1;i<=k;i++)ans=min(ans,D[i][n]);
}
int main(){
freopen("2662.in","r",stdin);
freopen("2662.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
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)
