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 ;
}