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

4rfc

Currency Exchange 　　大意：有多种货币，之间可以交换，但是需要手续费，也就是说既有汇率又有手续费。问经过交换之后能不能赚。
　　
　　思路：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 = 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.y] < (dis[Map.x]-Map.c)*Map.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\n");
72         }
73         else
74         {
75             printf("NO\n");
76         }
77     }
78 }
79
80 int main()
81 {
82     Solve();
83
84     return 0;
85 }
Currency Exchange