POJ 1860(spfa)

http://poj.org/problem?id=1860

题意:汇率转换,与之前的2240有点类似,不同的是那个题它去换钱的时候,是不需要手续费的,这个题是需要手续费的,这是个很大的不同。

思路:还是转换成为最短路的问题,主要的困难也就是关于它的松弛方程。dist [edge[i].v] < (dist[ tmp ] - edge[ i ].r) * edge[ i ].c  。这个就是松弛方程,当它的钱的数目增多的时候松弛。

 #include <stdio.h>
#include <string.h>
#include <queue> using namespace std; int m,n,p,head[ ],pos,num[ ];
bool vis[ ];
double val,dist[ ]; struct note{
int v,next;
double r,c;
}edge[ ]; void add(int x,int v,double r,double c)
{
edge[ pos ].v = v;
edge[ pos ].r = r;
edge[ pos ].c = c;
edge[ pos ].next = head[ x ];
head[ x ] = pos ++;
} bool spfa()
{
queue<int >s;
s.push(p);
dist[ p ] = val;
vis[ p ] = true;
num[ p ] ++;
while(!s.empty())
{
int tmp = s.front();
s.pop();
vis[ tmp ] = false;
for( int i = head[ tmp ] ; i != - ; i = edge[ i ].next)
{
if( dist[ edge[ i ].v ] < (dist[ tmp ] - edge[ i ].c ) * edge[ i ].r )
{
dist[ edge[ i ].v ] = (dist[ tmp ] - edge[ i ].c ) * edge[ i ].r;
if( !vis[ edge[ i ].v ] )
{
s.push( edge[ i ].v );
vis[ edge[ i ].v ] = true;
num[ edge[ i ].v ] ++; //可能构成正权回路,这个是用来判断的。但次数比m次要大的时候,就肯定是增多的。可以直接return 。
if( num[edge[ i ].v] > m)
return true;
}
}
}
}
if( dist[ p ] > val ) return true; //如果之后的钱比之前的多,也return true.
return false;
} int main()
{
// freopen("in.txt","r",stdin);
int a,b;
double r1,c1,r2,c2;
pos = ;
memset( head , - , sizeof( head ) );
memset( dist , , sizeof( dist ) );
memset( vis , false ,sizeof( vis ) );
memset( num , , sizeof( num ) );
scanf("%d%d%d%lf",&m,&n,&p,&val);
for( int i = ; i <= n ; i++ )
{
scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);
add(a,b,r1,c1);
add(b,a,r2,c2);
}
if(spfa()) printf("YES\n");
else printf("NO\n");
return ;
}
上一篇:Spring(Bean)4 配置数据源、连接池


下一篇:Microsoft Visual Studio 2013如何设置查找头文件的路径