pku3169 Layout

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