POJ-3169 Layout：http://poj.org/problem?id=3169
参考：https://blog.csdn.net/islittlehappy/article/details/81155802
题意：
一共有n头牛，有ml个关系好的牛的信息，有md个关系不好的牛的信息，对应输入的第一行的三个元素，接下来ml行，每行三个元素A,B,D，表示A牛和B牛相距不希望超过D，接下来md行，每行三个元素A,B,D表示A牛和B牛的相距至少要有D才行。求1号牛和n号牛的最大距离，如果距离无限大输出-2，如果无解输出-1。
思路：
设dis [ x ] 为x 到 0 位置的距离， v 的标号大于 u
我们要求 dis [ n ] - dis [ 1 ] <=x 即，x是n号牛与1号牛的最大距离
对于ml的关系好的牛有： dis [ v ] - dis [ u ] <= w; -------> dis [ v ] <= dis [ u ] + w; 建一条从u到v，权值为 w 边
对于md的关系差的牛有： dis [ v ] - dis [ u ] >= w; ---------> dis [ u ] <= dis [ v ] - w; 建一条从v到u，权值为 -w 边
则：我们的目标 是 dis [ v ] <= dis [ u ] + x; 若碰到 dis [ v ] > dis [ u ] + x 边进行松弛
因此，应该跑最短路
虽然还不知道差分约束具体是什么，但是还是觉得这种解法好神奇。
/* * @Author: chenkexing * @Date: 2018-09-05 11:05:14 * @Last Modified by: chenkexing * @Last Modified time: 2018-09-06 13:38:17 */ #include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> using namespace std; //#pragma GCC optimize(3) //#pragma comment(linker, "/STACK:102400000,102400000") //c++ #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << " "; #define pb push_back #define pq priority_queue typedef long long ll; typedef unsigned long long ull; typedef pair<ll ,ll > pll; typedef pair<int ,int > pii; typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q //priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q #define fi first #define se second //#define endl ' ' #define OKC ios::sync_with_stdio(false);cin.tie(0) #define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行 #define REP(i , j , k) for(int i = j ; i < k ; ++i) //priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+7; const double esp = 1e-8; const double PI=acos(-1.0); template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /*-----------------------showtime----------------------*/ const int maxn = 1e6+9; vector<pii>mp[maxn]; int in[maxn],cnt[maxn],dis[maxn],n; bool spfa(int s,int t){ memset(in,0,sizeof(in)); memset(dis,inf,sizeof(dis)); memset(cnt,0,sizeof(cnt)); queue<int>que;que.push(s); dis[s] = 0;in[s] = 1;cnt[s] ++; bool flag = false; while(!que.empty()){ int u = que.front();que.pop(); in[u] = 0; if(cnt[u] > n){ flag = true; break; } for(int i=0; i<mp[u].size(); i++){ int v = mp[u][i].fi; if(dis[v] > dis[u] + mp[u][i].se ){ dis[v] = dis[u] + mp[u][i].se; if(in[v] == 0){ in[v] = 1; que.push(v); cnt[v]++; } } } } if(flag)return true; return false; } int main(){ int m1,m2; scanf("%d%d%d", &n, &m1, &m2); for(int i=1; i<=m1; i++){ int u,v,w; scanf("%d%d%d", &u, &v, &w); mp[u].pb(pii(v,w)); } for(int i=1; i<=m2; i++){ int u,v,w; scanf("%d%d%d", &u, &v, &w); mp[v].pb(pii(u,-w)); } if(spfa(1,n) == false){ if(dis[n] >= inf)printf("-2 "); else printf("%d ", dis[n]); } else printf("-1 "); return 0; }