BZOJ 3245 最快路线

和道路升级差不多，只是用的spfa;

十分有毒，在BZOJ上一直WA，对拍拍出来是一样的却告诉我不一样，然后发现自己把'\n'写成了‘\b’。。。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

typedef long long LL;

const int maxm=+;

const int maxn=;

const int INF=1e9+;

using namespace std;

int ans,ecnt,n,m,t,u,v,lim,len,fir[maxn],nxt[maxm],to[maxm],val[maxm],li[maxm];

int vis[][],prx[][],prv[][],xx,vv,as[maxn];

double dp[][];

struct node {

    int id,v;

    node(){}

    node(int id,int v):id(id),v(v){}

}now;

void add(int u,int v,int lim,int w) {

    nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w; li[ecnt]=lim;

    //nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w; li[ecnt]=lim;

}

void init() {

    scanf("%d%d%d",&n,&m,&t);

    for(int i=;i<=m;i++) {

        scanf("%d%d%d%d",&u,&v,&lim,&len);

        add(u,v,lim,len);

    }

}

queue<node>que;

void spfa() {

    memset(vis,,sizeof(vis));

    memset(dp,,sizeof(dp));

    dp[][]=;

    que.push(node(,));

    while(!que.empty()) {

        now=que.front();

        que.pop();

        int x=now.id,v=now.v;

        vis[x][v]=;

        for(int i=fir[x];i;i=nxt[i]) {

            int y=to[i];

            if(li[i]&&dp[x][v]+(double)val[i]/li[i]<dp[y][li[i]]) {

                dp[y][li[i]]=dp[x][v]+(double)val[i]/li[i];

                prx[y][li[i]]=x; prv[y][li[i]]=v;

                if(!vis[y][li[i]]) {

                    vis[y][li[i]]=;

                    que.push(node(y,li[i]));

                }

            }

            else if(!li[i]&&dp[x][v]+(double)val[i]/v<dp[y][v]){

                dp[y][v]=dp[x][v]+(double)val[i]/v;

                prx[y][v]=x; prv[y][v]=v;

                if(!vis[y][v]) {

                    vis[y][v]=;

                    que.push(node(y,v));

                }

            }

        }

     }

}

void work() {

    spfa();

    for(int i=;i<=;i++) if(!vv||dp[t][i]<dp[t][vv]) vv=i;

    xx=t;

    for(;;) {

        as[++as[]]=xx;

        if(xx==) break;

        int tx=prx[xx][vv],tv=prv[xx][vv];

        xx=tx,vv=tv;

    }

    for(int i=as[];i>;i--)

     printf("%d ",as[i]);

    printf("%d\n",as[]);

}

int main()

{

    init();

    work();

    return ;

}