【题意】：给出n个防御站，它们都是从北到南排成一条直线。现在给出m个提示，精确的提示格式是 P A B X，表示A在B的北面X光年，模糊提示格式是V A B，表示A在B的北面至少一光年。现在问你，能有有可能安排这n个防御站同时满足m个提示？

【题解】：这题就是一道差分约束系统的裸题。
              对于输入的两种提示我们可以这样转化，随便选择一个方向吧，这不影响构图。
              1.P A B X  -> A - B == X -> A - B <= X && B - A <= -X
              2.V A B     -> A - B >= 1 -> B - A <= -1
              对于所有提示转化完不等式后构图求最短路，如果图中出现有负环则表示不能同时满足m个提示；否则可以满足。
              其实转化为求最长路也可以，具体做法可以看我那篇《差分约束系统总结》。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "queue"
 5 using namespace std;
 6 #define maxn 1005
 7 #define maxm 300000
 8 const int inf = 1 << 30;
 9 int n, m, s;
10 int dist[maxn], cnt[maxn], eh[maxn], tot;
11 char ch;
12 bool visit[maxn];
13 
14 struct Edge {
15     int u, v, w, next;
16 }et[maxm];
17 
18 void init() {
19     tot = 0;
20     memset(eh, -1, sizeof(eh));
21 }
22 
23 void addedge(int u, int v, int w) {
24     Edge e = {u, v, w, eh[u]};
25     et[tot] = e;
26     eh[u] = tot++;
27 }
28 
29 void spfa(int s, int n) {
30     memset(visit, false, sizeof(visit));
31     memset(cnt, 0, sizeof(cnt));
32     fill(&dist[0], &dist[maxn], inf);
33     dist[s] = 0, visit[s] = true; cnt[s]++;
34     queue<int> que;
35     que.push(s);
36     while(!que.empty()) {
37         int u = que.front();
38         que.pop();
39         visit[u] = false;
40         for(int i = eh[u]; i != -1; i = et[i].next) {
41             int v = et[i].v, w = et[i].w;
42             if(dist[v] > w + dist[u]) {
43                 dist[v] = w + dist[u];
44                 if(!visit[v]) {
45                     visit[v] = true;
46                     que.push(v);
47                     cnt[v]++;
48                     if(cnt[v] >= n) {
49                         printf("Unreliable\n");
50                         return;
51                     }
52                 }
53             }
54         }
55     }
56     printf("Reliable\n");
57 }
58     
59 int main() {
60     int u, v, x;
61     while(scanf("%d%d\n", &n, &m) != EOF) {
62         init();
63         for(int i = 0; i < m; i++) {
64             scanf("%c", &ch);
65             if(ch == 'P') {
66                 scanf("%d%d%d", &u, &v, &x);
67                 addedge(u, v, -x);
68                 addedge(v, u, x);
69             }
70             else {
71                 scanf("%d%d", &u, &v);
72                 addedge(u, v, -1);
73             }
74             getchar();
75         }
76         s = 0; //超级源点
77         for(int i = 1; i <= n; i++) addedge(s, i, 0);
78         spfa(s, n + 1);
79     }
80     return 0;
81 }