题目链接：POJ 3169 Layout
/*
题意：n头牛编号为1到n，按照编号的顺序排成一列，每两头牛的之间的距离 >= 0。
这些牛的距离存在着一些约束关系：
1.有ml组（u, v, w）的约束关系，表示牛[u]和牛[v]之间的距离必须 <= w。
2.有md组（u, v, w）的约束关系，表示牛[u]和牛[v]之间的距离必须 >= w。
问如果这n头无法排成队伍，则输出-1，如果牛[1]和牛[n]的距离可以无限远，则输出-2，
否则则输出牛[1]和牛[n]之间的最大距离。分析：
有三个约束关系：
隐含的：dis[i]<=dis[i+1],即dis[i+1]+0>=dis[i];
ML的： dis[b]-dis[a]<=c,即dis[a]+c>=dis[b](a<b);
MD的： dis[b]-dis[a]>=c,即dis[b]+(-c)>=dis[a](a<b).
然后依次建边，用spfa求最短路即可。
如果含有负环，那么就无法排成队伍，输出-1；
如果最短路不存在（dis[n]=INF),输出-2；
否则输出dis[n].*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;const int maxn = 1010;
const int maxm = 10010;
const int INF = 0x3f3f3f3f;int cnt[maxm];
int vis[maxn], head[maxn], dis[maxn];
int n, ml, md, tot, a, b, c;struct Edge {int v, w, next;
}edge[maxm];void AddEdge(int u, int v, int w, int k)
{edge[k].v = v;edge[k].w = w;edge[k].next = head[u];head[u] = k;
}int spfa(int s)
{stack<int> q;while (!q.empty()) q.pop();for (int i = 1; i <= n; i++) dis[i] = INF;dis[s] = 0;memset(vis, 0, sizeof(vis));vis[s] = 1;memset(cnt, 0, sizeof(cnt));q.push(s);while (!q.empty()){int u = q.top();q.pop();vis[u] = 0;for (int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;int w = edge[i].w;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;if (!vis[v]){vis[v] = 1;cnt[v]++;if (cnt[v] > n) return 0;//负环q.push(v);}}}}return 1;
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);
#endifwhile (~scanf("%d%d%d", &n, &ml, &md)){tot = 0;memset(head, -1, sizeof(head));for (int i = 1; i <= ml; i++){scanf("%d%d%d", &a, &b, &c);if (a > b) swap(a, b);AddEdge(a, b, c, tot++);}for (int i = 1; i <= md; i++){scanf("%d%d%d", &a, &b, &c);if (a > b) swap(a, b);AddEdge(b, a, -c, tot++);}for (int i = 1; i < n; i++)AddEdge(i + 1, i, 0, tot++);int flag = spfa(1);if (flag == 0) printf("-1\n");else{int ans = dis[n];if (ans == INF) ans = -2;printf("%d\n", ans);}}return 0;
}