最短路(Bellman_Ford) POJ 1860 Currency Exchange

hx0011yy

　　
　　题目传送门



1 /*
2     最短路(Bellman_Ford)：求负环的思路，但是反过来用，即找正环
3     详细解释：http://blog.iyunv.com/lyy289065406/article/details/6645778
4 */
5 #include <cstdio>
6 #include <iostream>
7 #include <algorithm>
8 #include <cstring>
9 #include <vector>
10 #include <cmath>
11 #include <queue>
12 #include <map>
13 #include <set>
14 using namespace std;
15
16 const int MAXN = 100 + 10;
17 const int INF = 0x3f3f3f3f;
18 const double EPS = 1e-8;
19 struct NODE
20 {
21     int u, v;
22     double r, c;
23 }node[MAXN*2];
24 double d[MAXN];
25
26 bool Bellman_Ford(int s, int n, int tot, double V)
27 {
28     memset (d, 0, sizeof (d));
29     d = V;
30     bool flag;
31     for (int i=1; i<=n-1; ++i)
32     {
33         flag = false;
34         for (int j=1; j<=tot; ++j)
35         {
36             NODE e = node[j];
37             if (d[e.v] < (d[e.u] - e.c) * e.r)
38             {
39                 d[e.v] = (d[e.u] - e.c) * e.r;    flag = true;
40             }
41         }
42         if (!flag)    break;
43     }
44
45     for (int i=1; i<=tot; ++i)
46     {
47         NODE e = node;
48         if (d[e.v] < (d[e.u] - e.c) * e.r)    return true;
49     }
50
51     return false;
52 }
53
54 int main(void)        //POJ 1860 Currency Exchange
55 {
56     //freopen ("A.in", "r", stdin);
57
58     int n, m, s;
59     double V;
60     while (~scanf ("%d%d%d%lf", &n, &m, &s, &V))
61     {
62         int tot = 0;
63         for (int i=1; i<=m; ++i)
64         {
65             int x, y;
66             double rab, cab, rba, cba;
67             scanf ("%d%d%lf%lf%lf%lf", &x, &y, &rab, &cab, &rba, &cba);
68             //printf ("%d %d %lf %lf %lf %lf\n", x, y, rab, cab, rba, cba);
69             node[++tot].u = x;    node[tot].v = y;
70             node[tot].r = rab;    node[tot].c = cab;
71             node[++tot].u = y;    node[tot].v = x;
72             node[tot].r = rba;    node[tot].c = cba;
73         }
74
75         if (Bellman_Ford (s, n, tot, V))    puts ("YES");
76         else    puts ("NO");
77     }
78
79     return 0;
80 }