poj 1860 Currency Exchange(最短経路の応用)

http://poj.org/problem?id=1860

   ：        ，  Rab，           Cab 。。。。。。。        (   -    ) *   ，                ，   value          ，        。







   ：

3 2 1 20.0                         //            ，      ，      

1 2 1.00 1.00 1.00 1.00            // a，  b， rab， cab， rba， cba

2 3 1.10 1.00 1.10 1.00



  ：   bellman-ford ：





           bellman      （    ）     （    ）   ，        - 1   ，             。   ，     。           （         ）







               ， bellman         ，         - 1   ，                    - 1     ，          ，                 ，    d[u] d[   (v)]   ，    ，          ，           。



              2  ： 



1。           ，              ，      d[x]    value    。

2。   d[x] 〉value ，            ，            ，          ，    。





  ，         



#include<stdio.h>

#define N 50000

#include<string.h>

#define max 999999

#define eps 1e-6

int n,m,x,vis[N],k;

double val,dis[N];//  dis  double

struct node

{

    int u,v;

    double r,c;

}p[N];

int bellman(int x)

{

    int i,f;

    memset(vis,0,sizeof(vis));

    for(i=0;i<=n;i++)

    {

        dis[i]=0;

    }

    dis[x]=val;

    while(dis[x]<=val+eps)

    {

        f=0;

        for(i=0;i<k;i++)

        {

            if(dis[p[i].v]+eps<(dis[p[i].u]-p[i].c)*p[i].r)

               {

                   dis[p[i].v]=(dis[p[i].u]-p[i].c)*p[i].r;

                   f=1;



               }

        }

        if(!f)return 0;//     

    }

    return 1;



}

int main()

{

   int i,u,v;

   double rvu,cvu,ruv,cuv;

    while(scanf("%d%d%d%lf",&n,&m,&x,&val)!=EOF)

    {

         k=0;

        for(i=0;i<m;i++)

        {

            scanf("%d%d%lf%lf%lf%lf",&u,&v,&ruv,&cuv,&rvu,&cvu);

            p[k].u=u;

            p[k].v=v;

            p[k].r=ruv;

            p[k].c=cuv;

            k++;

            p[k].u=v;

            p[k].v=u;

            p[k].r=rvu;

            p[k].c=cvu;

            k++;

        }



        int ans=bellman(x);

        if(ans)printf("YES
");

        else printf("NO
");

    }

}