POJ 1860 Currency Exchange(最短路 Bellman-Ford)

大意：有多种货币，之间可以交换，但是需要手续费，也就是说既有汇率又有手续费。问经过交换之后能不能赚。

思路：Bellman_Ford，因为要求最长路，所以松弛条件改一下就好了。

Tips：

3              2                  1                20.0
货币的数量   兑换点的数量     主人公拥有的货币量    主人公拥有货币的价值
1 2 1.00 1.00 1.00 1.00
//货币1与货币2交换时，1与2的汇率是1.00,1换2的手续费是1.00,2与1的汇率是1.00,2换1的手续费是1.00。
2 3 1.10 1.00 1.10 1.00
//货币1与货币2交换时，1与2的汇率是1.10,1换2的手续费是1.00,2与1的汇率是1.10,2换1的手续费是1.00。

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <map>
 4 #include <stack>
 5 #include <string.h>
 6 #define INF 0x3f3f3f3f
 7 using namespace std;
 8 
 9 int n, m, s;
10 double v;
11 double dis[110];
12 int t;
13 
14 struct node
15 {
16     int x, y;
17     double r, c;
18 } Map[210];
19 
20 bool Bellman_Ford()
21 {
22     memset(dis, 0, sizeof(dis));
23     dis[s] = v;
24     for(int i = 1; i <= n-1; i++)
25     {
26         bool flag = false;
27         for(int j = 0; j < t; j++)
28         {
29             if(dis[Map[j].y] < (dis[Map[j].x]-Map[j].c)*Map[j].r)
30             {
31                 dis[Map[j].y] = (dis[Map[j].x]-Map[j].c)*Map[j].r;
32                 flag = true;
33             }
34         }
35         if(!flag)
36         {
37             break;
38         }
39     }
40     for(int i = 0; i < t; i++)
41     {
42         if(dis[Map[i].y] < (dis[Map[i].x]-Map[i].c)*Map[i].r)
43         {
44             return true;
45         }
46     }
47     return false;
48 }
49 
50 void Solve()
51 {
52     int a, b;
53     double Rab, Rba, Cab, Cba;
54     while(~scanf("%d%d%d%lf", &n, &m, &s, &v))
55     {
56         t = 0;
57         for(int i = 0; i < m; i++)
58         {
59             scanf("%d%d%lf%lf%lf%lf", &a, &b, &Rab, &Cab, &Rba, &Cba);
60             Map[t].x = a;
61             Map[t].y = b;
62             Map[t].r = Rab;
63             Map[t++].c = Cab;
64             Map[t].x = b;
65             Map[t].y = a;
66             Map[t].r = Rba;
67             Map[t++].c = Cba;
68         }
69         if(Bellman_Ford())
70         {
71             printf("YES
");
72         }
73         else
74         {
75             printf("NO
");
76         }
77     }
78 }
79 
80 int main()
81 {
82     Solve();
83 
84     return 0;
85 }

Currency Exchange