poj 1860 Currency Exchange SPFA

ddlddx0000

　　算法：
　　1.SPFA求最长路，dis【】初始直为0，大于改成小于号
　　2.松弛结束后，判断是否大于dis[S] > 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[MAXN];

int N, M, S, head[MAXN], visit[MAXN], hash[MAXN], size;
double V, dis[MAXN];

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[size] = Edge( v, head, val1, Cost1);
head = size++;
edge[size] = Edge( u, head[v], val2, Cost2);
head[v] = size++;     

}

void SPFA( )
{
queue<node>q;
node p;
p.ID = S;
p.money = V;
q.push( p );
dis[S] = V;
hash[S] = 1;
while( !q.empty())
{
p = q.front( );
q.pop( );
int v = p.ID;
double money = dis[v];
visit[v] = 0;
for( int e = head[v]; e != -1; e = edge[e].next)
{
int v = edge[e].u;
double rate = edge[e].val;
double cost = edge[e].cost;
double xx = rate * ( money - cost );
if( dis[v] < xx )
{
dis[v] = xx;
if( !visit[v] )
{
p.ID = v;
p.money = dis[v];
q.push( p );
visit[v] = 1;
hash[v]++;        

}

}      

}

}
if( fabs(dis[S]) - V > 0 )
puts("YES");
else
puts("NO");

}

int  main( )
{
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;   
}