Currency Exchange--POJ 1860
1、题目类型：图论、最短路径、Bellman-Ford算法。2、解题思路：Bellman-Ford算法简单应用。
3、注意事项：更新条件：d<(d-com)*rate。
4、实现方法:
#include<iostream>
using namespace std;
#define Max 110
#define INF 99999999.9
int n,m,s,flag;
double v;
double rate,com;
void Bellman_ford()
{
int i,j,k;
double d;
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<(d-com)*rate)
d=(d-com)*rate;
flag=0;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (d<(d-com)*rate)
{
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>>com;
cin>>rate>>com;
}
Bellman_ford();
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 1;
}
页:
[1]