Currency Exchange--POJ 1860

woxio770

　　1、题目类型：图论、最短路径、Bellman-Ford算法。
　　2、解题思路：Bellman-Ford算法简单应用。
　　3、注意事项：更新条件：d[j]<(d-com[j])*rate[j]。
　　4、实现方法:




#include<iostream>
using namespace std;
#define Max 110
#define INF 99999999.9
int n,m,s,flag;
double v;
double rate[Max][Max],com[Max][Max];
void Bellman_ford()
{
    int i,j,k;
    double d[Max];
    for (i=0;i<n;i++)
        d=-INF;
    s--;
    d=v;
    for (k=1;k<n;k++)
        for (i=0;i<n;i++)
            for (j=0;j<n;j++)
                if (d[j]<(d-com[j])*rate[j])
                    d[j]=(d-com[j])*rate[j];
    flag=0;
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            if (d[j]<(d-com[j])*rate[j])
            {
                flag=1;
                return;
            }
    if(d>v)
        flag=1;
}
int main()
{
    int i,tmp1,tmp2;
    cin>>n>>m>>s>>v;
    for(i=0;i<m;i++)
    {
        cin>>tmp1>>tmp2;
        tmp1--,tmp2--;
        cin>>rate[tmp1][tmp2]>>com[tmp1][tmp2];
        cin>>rate[tmp2][tmp1]>>com[tmp2][tmp1];
    }
    Bellman_ford();
    if(flag)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 1;
}