Currency Exchange poj1860

wcdz

　　   个人认为这是一道比较好的题目，考虑了很多知识点。很显然题目是要求一种兑换方案使最后的钱最多，但如果我们将钱数都取其相反数，那么反过来就是求最小的钱数了（当然此时的钱数是个负数了，不过为了叙述方便，我们就暂且认定钱可以为负吧）。到了这里还存在一个问题，在已知的一种兑换方案中一旦存在负环，那么该方案就不存在最小钱数了，因为它可以无限小，则该方案肯定满足题意。
　　所以该题在求出最短路径后，应该还要判断是否存在负环，而且负环应至少有一个顶点在某一种兑换方案所在的路径上，即此题还要求出一个包含s点的连通子图。
　　PS：此题作为单源最短路径的题目，因为起点和终点是同一个点，所以此处我将起点拆成了两个点。

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
struct
{
int a,b;
double r,c;
}map[205];
double d[105];
vector<int>map1[105];//邻接表
bool visit[105];
int n,m,s;
double v;
bool relax(int u,int v,double r,double c)
{
if((d+c)*r<d[v])
{
d[v]=(d+c)*r;
return true;
}
return false;
}
//此处是为了求出与s连通的点，用visit数组标记是否连通
void dfs(int u)
{
visit=true;
for(int i=0;i<map1.size();i++)
if(!visit[map1])
dfs(map1);
}
int main()
{
int i,j,a,b;
while(~scanf(&quot;%d%d%d%lf&quot;,&n,&m,&s,&v))
{
for(i=1;i<=n+1;i++)
map1.clear();
i=0;
while(m--)
{
scanf(&quot;%d%d&quot;,&a,&b);
map.a=a;map.b=b;
if(map.b==s)
map.b=n+1;
scanf(&quot;%lf%lf&quot;,&map.r,&map.c);
map1[map.a].push_back(map.b);
i++;
map.a=b;map.b=a;
if(map.b==s)
map.b=n+1;
scanf(&quot;%lf%lf&quot;,&map.r,&map.c);
map1[map.a].push_back(map.b);
i++;
}
m=i;
for(i=1;i<=n+1;i++)
d=100000000.0;
d=-v;
for(i=1;i<n;i++)
for(j=0;j<m;j++)
relax(map[j].a,map[j].b,map[j].r,map[j].c);
if(-d[n+1]>v)
{
printf(&quot;YES\n&quot;);
continue;
}
for(i=1;i<=n+1;i++)
visit=false;
//此处判断负环，若有负环，则肯定可以满足，当然要保证负环中有至少一个顶点在dfs求得的子连通图中
dfs(s);
for(j=0;j<m;j++)
if((visit[map[j].a]||visit[map[j].b])&&relax(map[j].a,map[j].b,map[j].r,map[j].c))
{
printf(&quot;YES\n&quot;);
break;
}
if(j==m)
printf(&quot;NO\n&quot;);
}
return 0;
}