【SPFA】POJ1860-Currency Exchange

【题目大意】

给出每两种货币之间交换的手续费和汇率，求出从当前货币s开始交换，能否赚。

【思路】

反向运用SPFA，判断是否有正环。每次队首元素出队之后，判断一下到源点s的距离是否增大，增大则返回true。一开始判断正环的思路如果有一个元素入队超过n次，则说明存在正环。后来发现这个思路是不适用的，因为这个正环中并不一定包含源点..要注意的是：题目中的m并不是边数，边数应该是m*2！所以开数组的时候要尤其注意数组不能开小了。由于C++的判定中如果没有崩掉，不会返回RE只会返回WA，我纠结了好久才找出错因。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 struct Rec

 {

     int ori,des;

     double len,val;

 };

 const int MAXN=+;

 int first[MAXN],next[MAXN*];

 /*用于存储邻接表*/

 double dis[MAXN];

 /*存储从s出发到达当前货币的最大值*/

 int vis[MAXN];

 /*判断某一个点是否已经存在于队列中*/

 Rec edge[MAXN*];

 int n,m,s;

 double v;

 bool SPFA()

 {

     memset(dis,,sizeof(dis));

     memset(vis,,sizeof(vis));

     queue<int> que;

     dis[s]=v;

     /*默认到持有货币的距离为持有货币的价值*/

     vis[s]=;

     que.push(s);

     while (!que.empty())

     {

         int pos=que.front();

         int k=first[pos];

         vis[pos]=;

         que.pop();

         while (k!=-)

         {

             if (dis[edge[k].des]<(dis[pos]-edge[k].len)*edge[k].val)

             {

                 dis[edge[k].des]=(dis[pos]-edge[k].len)*edge[k].val;

                 if (!vis[edge[k].des])

                 {

                     vis[edge[k].des]=;

                     que.push(edge[k].des);

                 }

             }

             k=next[k];

         }

         if (dis[s]>v) return true;

     }

     return false;

 }

 int main()

 {

     scanf("%d%d%d%lf",&n,&m,&s,&v);

     s--;

     memset(first,-,sizeof(first));

     for (int i=;i<m;i++)

     {

         int a,b;

         double c1,r1,c2,r2;

         scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);

         a--;

         b--;

         edge[i*].ori=edge[i*+].des=a;

         edge[i*].des=edge[i*+].ori=b;

         edge[i*].val=r1;

         edge[i*].len=c1;

         edge[i*+].val=r2;

         edge[i*+].len=c2;

         next[i*]=first[a];

         first[a]=i*;

         next[i*+]=first[b];

         first[b]=i*+;

     }

     m=m*+;

     if (SPFA()) cout<<"YES"<<endl;

                 else cout<<"NO"<<endl;

     //system("pause");

     return ;

 }