POJ 3169 Layout(差分约束系统)

这道题是经典的差分约束系统，这道题可以看到明确的其源点1，所以求解的是从1出发终点为n的最短路。

差分约束系统有两种方式可求解，最短路和最长路。当我们把不等式整理成d[a]+w<=d[b]时，我们求最长路。

整理成d[a]+w>=d[b]时，我们求最短路。

当求最短路时，我们通常要把各点距离初始化为正无穷，求最短路，把各点距离逐渐减小，直到符合所有不等式。

代码：

1 #include <algorithm>
2 #include <iostream>
3 #include <cstring>
4 #include <cstdio>
5 #include <queue>
6 using namespace std;
7 const int maxn=10010;
8 const int inf=0x7fffffff;
9 struct node
10 {
11     int v;
12     int u;
13     int next;
14 }edge[maxn<<1];
15 int head[maxn],dist[maxn],cnt[maxn],vis[maxn];
16 int p,n,ml,md,max;
17 queue <int> q;
18 void add(int a,int b,int c)
19 {
20     edge[p].v=b;
21     edge[p].u=c;
22     edge[p].next=head[a];
23     head[a]=p;
24     p++;
25 }
26 int spfa()
27 {
28     int k;
29     dist[1]=0;
30     vis[1]=1;
31     q.push(1);
32     cnt[1]++;
33     while(!q.empty())
34     {
35         k=q.front();
36         q.pop();
37         vis[k]=0;
38         for(p=head[k];p!=-1;p=edge[p].next)
39         {
40             if(dist[edge[p].v]>dist[k]+edge[p].u)
41             {
42                 dist[edge[p].v]=dist[k]+edge[p].u;
43                 if(!vis[edge[p].v])
44                 {
45                     if(++cnt[edge[p].v]>n)
46                         return 0;
47                     vis[edge[p].v]=1;
48                     q.push(edge[p].v);
49                 }
50             }
51         }
52     }
53     return 1;
54 }
55 void init()
56 {
57     int i;
58     for(i=1;i<=n;i++)
59         dist[i]=inf;
60     memset(head,-1,sizeof(head));
61     memset(vis,0,sizeof(vis));
62 }
63 int main()
64 {
65     int i,a,b,c;
66     while(~scanf("%d%d%d",&n,&ml,&md))
67     {
68         init();
69         p=0;
70         for(i=0;i<ml;i++)
71         {
72             scanf("%d%d%d",&a,&b,&c);
73             add(a,b,c);
74         }
75         for(i=0;i<md;i++)
76         {
77             scanf("%d%d%d",&a,&b,&c);
78             add(b,a,-c);
79         }
80         for(i=1;i<n;i++)
81             add(i+1,i,0);
82         if(!spfa())
83             puts("-1");
84         else if(dist[n]-dist[0]>=inf)
85             puts("-2");
86         else
87             printf("%d\n",dist[n]-dist[0]);
88     }
89     return 0;
90 }