> #include <iostream>
> #include <queue>
> using namespace std;
> const double eps=1e-6;
> double R[105][105],C[105][105],V;
> int N,M,S;
> 
> bool SPFA(){
>        double val[105];
>        memset(val,0,sizeof(val));
>        while (val[S]<V+eps){
>               bool b=false;
>               int u;
>               int count[105];
>               memset(count,0,sizeof(count));
>               val[S]=V;
>               queue <int >Q;
>               Q.push(S);
>               bool isIn[105];
>               isIn[S]=1;
>               memset(isIn,0,sizeof(isIn));
>               while (!Q.empty()){
>                      u=Q.front(),Q.pop();
>                      isIn[u]=0;
>                      if (count[u]>N)break;
>                      for (int v=1;v<=N;v++){
>                             if ( (val[u]-C[u][v])*R[u][v] > val[v]+eps && !isIn[v]){
>                                    val[v]=(val[u]-C[u][v])*R[u][v];
>                                    b=true;
>                                    Q.push(v);
>                                    count[v]++;
>                             }
>                      }
>               }
>               if (!b){
>                      break;
>               }
>        }
>        if (val[S]>V+eps){
>               printf("YES\n");
>        }
>        else{
>               printf("NO\n");
>        }
> }
> 
> int main(){
>        scanf("%d%d%d",&N,&M,&S);
>        scanf("%lf",&V);
>        double Rab,Rba,Cab,Cba;
>        int A,B;
>        for (int i=0;i<M;i++){
>               scanf("%d%d%lf%lf%lf%lf",&A,&B,&Rab,&Cab,&Rba,&Cba);
>               R[A][B]=Rab,R[B][A]=Rba;
>               C[A][B]=Cab,C[B][A]=Cba;
>        }
>        SPFA();
>        return 0;
> }

• Re:BellmanFord AC，SPFA为什么就WA呢？麻烦用SPFA过的同学给发份代码，或者给我看看，谢谢 (0) talewoods 2015-02-02 07:55:02