POJ 1860 Currency Exchange Bellman-Ford

zhangbinmy

　　题意：能否通过套汇盈利。

题解：

#include <iostream>
using namespace std;
double dist[210], v;
int n, m, s;
struct item
{
int a, b;
double r,c;
} node[210];
bool Bellman_ford ()
{
int i, j;
memset(dist,0,sizeof(dist));
dist = v;
for ( i = 1; i < n; i++ )
{
for ( j = 1; j <= m * 2; j++ )
if ( dist[node[j].b] < ( dist[node[j].a] - node[j].c ) * node[j].r )
dist[node[j].b] = ( dist[node[j].a] - node[j].c ) * node[j].r;
}
for ( j = 1; j <= m * 2; j++ )
if ( dist[node[j].b] < ( dist[node[j].a] - node[j].c ) * node[j].r )
return true;
return false;
}
int main()
{
int a, b;
double r1, r2, c1, c2;
cin >> n >> m >> s >> v;
for ( int i = 1; i <= m * 2; i++ )
{
cin >> a >> b >> r1 >> c1 >> r2 >> c2;
node.a = a;
node.b = b;
node.r = r1;
node.c = c1;
i++;
node.a = b;
node.b = a;
node.r = r2;
node.c = c2;
}
if ( Bellman_ford () )
cout << &quot;YES&quot; << endl;
else
cout << &quot;NO&quot; << endl;
return 0;
}