pku1860 Currency Exchange

http://poj.org/problem?id=1860
图论，SPFA
好题
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #define N 1000100
 5 
 6 using namespace std;
 7 
 8 int n, m, src;
 9 int x[N], y[N], len[N];
10 float dist[N];
11 bool inQue[N];
12 queue<int> que;
13 const int inf = 1<<30;
14 vector<pair<int, pair<float, float> > > g[N];
15 int count[N];
16 float src0;
17 
18 int spfa()
19 {
20     int i;
21     for(i=0; i<N; i++)
22     {
23         inQue[i] = false;
24         dist[i] = 0;
25         count[i] = 0;
26     }
27     dist[src] = src0;
28     while(!que.empty())
29     {
30         que.pop();
31     }
32     que.push(src);
33     count[src] ++;
34     inQue[src] = true;
35     while(!que.empty())
36     {
37         int u = que.front();
38         que.pop();
39         for(i=0; i<g[u].size(); i++)
40         {
41             if((dist[u]-g[u][i].second.second)*g[u][i].second.first > dist[g[u][i].first])
42             {
43                 dist[g[u][i].first] = (dist[u]-g[u][i].second.second)*g[u][i].second.first;
44                 if(!inQue[g[u][i].first])
45                 {
46                     inQue[g[u][i].first] = true;
47                     que.push(g[u][i].first);
48                     count[g[u][i].first] ++;
49                     if(count[g[u][i].first] > n)
50                     {
51                         return -1;
52                     }
53                 }
54             }
55         }
56         inQue[u] = false;
57     }
58     return 0;
59 }
60 
61 
62 int main()
63 {
64     int x, y, t, i, j;
65     float x1, x2, y1, y2;
66     scanf("%d%d%d%f", &n, &m, &src, &src0);
67     for(i=1; i<=m; i++)
68     {
69         scanf("%d%d%f%f%f%f", &x, &y, &x1, &x2, &y1, &y2);
70         g[x].push_back(make_pair(y, make_pair(x1, x2)));
71         g[y].push_back(make_pair(x, make_pair(y1, y2)));
72     }
73     if(spfa() == -1)
74     {
75         printf("YES\n");
76     }
77     else
78     {
79         printf("NO\n");
80     }
81     return 0;
82 }