4
22
2016
0

[BZOJ2763] [JLOI2011]飞行路线

分层图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;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 606

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com