Bellman-Ford算法：POJ No.3169 Layout 差分约束

 1 #define _CRT_SECURE_NO_WARNINGS
 2 /*
 3 4 2 1
 4 1 3 10 2 4 20
 5 2 3 3
 6 */
 7 #include <iostream>
 8 #include <algorithm>
 9 #include <cstdio>
10 #include <cstdlib>
11 using namespace std;
12 
13 const int maxn = 10000 + 200;
14 const int INF = 999999;
15 //输入
16 int N, ML, MD;
17 int AL[maxn], BL[maxn], DL[maxn];
18 int AD[maxn], BD[maxn], DD[maxn];
19 
20 int d[maxn];
21 
22 void solve()
23 {
24     fill(d, d + N, INF);
25     d[0] = 0;
26 
27     //用Bellman-Ford算法计算d
28     for (int k = 0; k < N; k++) {
29         //从i+1到i的权值为0
30         for (int i = 0; i + 1 < N; i++) {
31             if (d[i + 1] < INF) d[i] = min(d[i], d[i + 1]);
32         }
33         //从AL到BL的权值为DL
34         for (int i = 0; i < ML; i++) {
35             if (d[AL[i] - 1] < INF) {
36                 d[BL[i] - 1] = min(d[BL[i] - 1], d[AL[i] - 1] + DL[i]);
37             }
38         }
39         //从BD到AD的权值为-DD
40         for (int i = 0; i < MD; i++) {
41             if (d[BD[i] - 1] < INF) {
42                 d[AD[i] - 1] = min(d[AD[i] - 1], d[BD[i] - 1] - DD[i]);
43             }
44         }
45     }
46     int res = d[N - 1];
47     if (d[0] < 0) {
48         //存在负边无解
49         res = -1;
50     }
51     else if (res == INF) {
52         res = -2;
53     }
54     printf("%d
", res);
55 }
56 
57 void input()
58 {
59     cin >> N >> ML >> MD;
60     for (int i = 0; i < ML; i++) {
61         cin >> AL[i] >> BL[i] >> DL[i];
62     }
63     for (int i = 0; i < MD; i++) {
64         cin >> AD[i] >> BD[i] >> DD[i];
65     }
66 }
67 
68 int main()
69 {
70     input();
71     solve();
72     return 0;
73 }