poj 1860 Currency Exchange SPFA
算法：1.SPFA求最长路，dis【】初始直为0，大于改成小于号
2.松弛结束后，判断是否大于dis > V， 大于就输出YES， 否则输出NO
View Code
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#include <math.h>
#include <algorithm>
#define MAXN 100100
using namespace std;
struct Edge
{
int u, next;
double val, cost;
Edge( ) { }
Edge( int U, int Next, double Val, double Cost): u(U), next(Next), val(Val), cost(Cost) {}
}edge;
int N, M, S, head, visit, hash, size;
double V, dis;
struct node
{
int ID;
// double rate;
double money;
// double c;
};
void init( )
{
for( int i = 0; i < MAXN; i++)
{
head = -1;
dis = 0;
visit = 0;
hash = 0;
}
size = 0;
}
void AddEdge( int u, int v, double val1, double val2, double Cost1, double Cost2)
{
edge = Edge( v, head, val1, Cost1);
head = size++;
edge = Edge( u, head, val2, Cost2);
head = size++;
}
void SPFA( )
{
queue<node>q;
node p;
p.ID = S;
p.money = V;
q.push( p );
dis = V;
hash = 1;
while( !q.empty())
{
p = q.front( );
q.pop( );
int v = p.ID;
double money = dis;
visit = 0;
for( int e = head; e != -1; e = edge.next)
{
int v = edge.u;
double rate = edge.val;
double cost = edge.cost;
double xx = rate * ( money - cost );
if( dis < xx )
{
dis = xx;
if( !visit )
{
p.ID = v;
p.money = dis;
q.push( p );
visit = 1;
hash++;
}
}
}
}
if( fabs(dis) - V > 0 )
puts("YES");
else
puts("NO");
}
intmain( )
{
int a, b;
double rab, cab, rba, cba;
while( scanf("%d%d%d%lf",&N, &M, &S, &V) != EOF)
{
init( );
for( int i = 1; i <= M; i++)
{
scanf("%d%d%lf%lf%lf%lf",&a, &b, &rab, &cab, &rba, &cba);
AddEdge( a, b, rab, rba, cab, cba);
}
SPFA( );
}
return 0;
}
页:
[1]