很久以前写的题目了……
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;
}
评论 (0)
