POJ 1860 Currency Exchange逆bellman-ford

1つの都市の中でnの中の貨幣が存在して、番号1からn、貨幣の間で両替することができて、2種類の貨幣の間の両替率はrで、両替する時の手数料はcで、これはもしあなたが100ドルがルーブルに両替したいならば、ドルとルーブルの間の両替率は29.75で、手数料は0.39ならば、あなたは(100-0.39)*29.75=29.63.3975ルーブルを得ることができます.現在、n種類の通貨とm中の通貨との間の両替関係が知られており、各両替関係には、互いに両替可能な2種類の通貨aとbと、通貨a対bの為替レートr 1、手数料c 1、および通貨b対aの為替レートr 2、手数料c 2が含まれる.最初に持っていた通貨の種類sと価値vを与え、何回かの通貨両替の後、再びs通貨に両替したときの価値v 1がvを超えるかどうかを尋ねます.
分析:HDU 1217問題と少し似ています.同じ通貨両替ですが、この問題で手数料が増えただけで、また繰り返し両替できます(与えられた例からわかります).しかし、この2つの問題の思想は同じで、私たちはすべての通貨を1つの点と見なして、2つの通貨の間の両替値を2つの点の間の権値と見なして、このようにして、問題を“最短の経路”の問題に転化しました.ある辺を繰り返すことができて、しかも探している値は“最大値”で、甚だしきに至っては無限の大きさで、少し見覚えのある感じではありませんか?bellman‐fordアルゴリズムにおける負の重み回路を判断する方法は,無限に緩和できるためであり,n‐1サイクル後も決定値がないためであり,重み値を比較する過程で記録間の大きな値を比較すると,この方法で図中の正の重み回路があるかどうかを判断できる(無限に緩和でき,無限に増加できる).
実装コードは次のとおりです.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef struct node
{
    int u,v;
    double r,c;
}EDGE;
EDGE edge[220];
int n,m,start;
double sv;
double w[110];
void add(int u,int v,double r,double c)
{
    m++;
    edge[m].u=u;
    edge[m].v=v;
    edge[m].r=r;
    edge[m].c=c;
}
bool bellman_ford()
{
    memset(w,0,sizeof(w));
    w[start]=sv;
    for(int i=1;i<n;i++)
      for(int j=1;j<=m;j++)
        if(w[edge[j].v]<(w[edge[j].u]-edge[j].c)*edge[j].r)
          w[edge[j].v]=(w[edge[j].u]-edge[j].c)*edge[j].r;
    bool flag=false;
    for(int i=1;i<=m;i++)
      if(w[edge[i].v]<(w[edge[i].u]-edge[i].c)*edge[i].r)
      {
          flag=true;
          break;
      }
    return flag;
}
int main()
{
    int m1,a,b;
    double r1,r2,c1,c2;
    scanf("%d%d%d%lf",&n,&m1,&start,&sv);
    m=0;
    for(int i=0;i<m1;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(bellman_ford()) puts("YES");
    else puts("NO");
    return 0;
}