#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过的同学给发份代码，或者给我看看，谢谢 (34) YA_ME_DE 2009-05-06 13:55:56
  • Re: 你确实 SPFA 写错勒 附上 错误 部分代码 (563) __sunshine 2009-05-20 13:25:16
• Re:BellmanFord AC，SPFA为什么就WA呢？麻烦用SPFA过的同学给发份代码，或者给我看看，谢谢 (1789) kidjelly 2010-01-10 16:12:12
  • Re:BellmanFord AC，SPFA为什么就WA呢？麻烦用SPFA过的同学给发份代码，或者给我看看，谢谢 (0) talewoods 2015-02-02 07:55:02
• Re:BellmanFord AC，SPFA为什么就WA呢？麻烦用SPFA过的同学给发份代码，或者给我看看，谢谢 (1789) kidjelly 2010-01-10 16:12:14
  • Re:BellmanFord AC，SPFA为什么就WA呢？麻烦用SPFA过的同学给发份代码，或者给我看看，谢谢 (6) kidjelly 2010-01-10 16:12:50