3
9
2016
0

[BZOJ3245] 最快路线

很久以前写的题目了……

SPFA

显然的算法啊

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
  
int fa[155][155],n,m,d,h[155],en=0,f[155][155];
double D[155][155];
  
struct Edge{
int b,v,l,next;
}e[30005];
  
struct Queue{
int speed,i,j;
};
  
void shuchu(int u,int v,int f){
if(u==v && v==0){printf("0 ");return;}
shuchu(fa[u][v],u,0);
if(f==0)printf("%d ",v);
else printf("%d\n",v);
}
  
void add(int as,int bs,int vs,int ls){
e[++en].b=bs;
e[en].v=vs;
e[en].l=ls;
e[en].next=h[as];
h[as]=en;
}
  
void spfa(){
queue<Queue> Q;
Queue pos;
pos.i=0;
pos.j=0;
pos.speed=70;
Q.push(pos);
int u,v;
D[0][0]=0;
f[0][0]=1;
while(!Q.empty()){
    Queue uu;
    uu=Q.front();
    u=uu.j;
    Q.pop();
    f[uu.i][u]=0;
    for(int i=h[uu.j];i;i=e[i].next){
        v=e[i].b;
        int speed=e[i].v;
        if(e[i].v<=0)speed=uu.speed;
        if(D[u][v]>D[uu.i][u]+(double)e[i].l/(double)speed){
            D[u][v]=D[uu.i][u]+(double)e[i].l/(double)speed;
            fa[u][v]=uu.i;
            if(!f[u][v]){
                f[u][v]=1;
                pos.i=u;
                pos.j=v;
                pos.speed=speed;
                Q.push(pos);
            }
        }
    }
}
}
  
int main(){
freopen("3245.in","r",stdin);
freopen("3245.out","w",stdout);
scanf("%d %d %d",&n,&m,&d);
memset(D,0x7f,sizeof(D));
for(int i=0;i<m;i++){
    int as,bs,vs,ls;
    scanf("%d %d %d %d",&as,&bs,&vs,&ls);
    add(as,bs,vs,ls);
}
spfa();
double mind=99999999999999.0;
int ans;
for(int i=0;i<n;i++){
    if(mind>D[i][d]){
        ans=i;
        mind=D[i][d];
    }
}
shuchu(ans,d,1);
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 571

登录 *


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