POJ 3169 Layout

http://poj.org/problem?id=3169

//转化为有向图求最短路
//这道题加深对Bellman_ford使用和理解
//但是太难了感觉确实 -->> 确实是差分约束系统的题但是刚好和最短路的推导形式相符

最短路的推导

如果u v之间有cost = w的边e(u,v)

dist[v] = min(dist[v], dist[u]+w);

那么如下理解

// i 和 i+1有一条为0的边
// AL+DL >= BL ALi 和 BLi之间有一条权重为DLi的边
// AD+DD <= BD --->> BD - DD >= AD --->> ADi 和 BDi之间有一条权重为-DDi的边

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define READ() freopen("in.txt", "r", stdin);
 5 #define MAXV 10007
 6 #define INF 0x3f3f3f3f
 7 using namespace std;
 8 
 9 int AL[MAXV], BL[MAXV], DL[MAXV];
10 int AD[MAXV], BD[MAXV], DD[MAXV];
11 int N, ML, MD;
12 
13 
14 int Bellman_ford()
15 {
16     int dist[MAXV];
17     fill(dist, dist+MAXV, INF);
18     dist[1] = 0;
19     for (int k = 0; k < N; k++)//最多循环k-1次 Bellman_ford就是 在这k-1次循环中 遍历所有的边
20     {
21         for (int i = 1; i < N; i++) // i 和 i+1有一条为0的边
22             if (dist[i+1] < INF) dist[i] = min(dist[i], dist[i+1]);
23         for (int i = 0; i < ML; i++) // AL+DL >= BL ALi 和 BLi之间有一条权重为DLi的边
24             if (dist[AL[i]] < INF) dist[BL[i]] = min(dist[BL[i]], dist[AL[i]] + DL[i]);
25         for (int i = 0; i < MD; i++) // AD+DD <= BD --->> BD - DD >= AD --->> ADi 和 BDi之间有一条权重为-DDi的边
26             if (dist[BD[i]] < INF) dist[AD[i]] = min(dist[AD[i]], dist[BD[i]] - DD[i]);
27     }
28     if (dist[1] < 0)
29         return -1;//有负圈
30     else if (dist[N] == INF)
31         return -2;//无法到达
32     else return dist[N];
33 }
34 
35 
36 
37 int main()
38 {
39     READ();
40     scanf("%d%d%d", &N, &ML, &MD);
41     for (int i = 0; i < ML; i++)
42     {
43         scanf("%d%d%d", &AL[i], &BL[i], &DL[i]);
44     }
45     for (int i = 0; i < MD; i++)
46     {
47         scanf("%d%d%d", &AD[i], &BD[i], &DD[i]);
48     }
49     int ans = Bellman_ford();
50     cout << ans << endl;
51 
52 }