题意
当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。即使说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。
一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数L。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述，再给出MD条关于两头奶牛间存有反感的描述。（1<=ML,MD<=10000，1<=L,D<=1000000） 你的工作是：如果不存在满足要求的方案，输出-1；如果1号奶牛和N号 奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，1号奶牛和N号奶牛间可能的最大距离。题解
差分约束，第一种A向B连权值为v的边，第二种B向A连-v的边。
SPFA当有环时，-2；跑不到n， -1 我打的是DFS常数巨大的丑陋代码
# include# include # include # include # include # define RG register# define IL inline# define ll long long# define mem(a, b) memset(a, b, sizeof(a))# define Min(a, b) (((a) > (b)) ? (b) : (a))# define Max(a, b) (((a) < (b)) ? (b) : (a))using namespace std;IL int Get(){ RG char c = '!'; RG int x = 0, z = 1; for(; c > '9' || c < '0'; c = getchar()) z = c == '-' ? -1 : 1; for(; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + c - '0'; return x * z;}const int MAXN = 1001, MAXM = 20001, INF = 2147483647;int n, dis[MAXN], vis[MAXN], ft[MAXN], m1, cnt, m2, flag;struct Edge{ int to, f, nt;} edge[MAXM];IL void Add(RG int u, RG int v, RG int f){ edge[cnt] = (Edge){v, f, ft[u]}; ft[u] = cnt++;}IL void Dfs(RG int u){ vis[u] = 1; if(flag) return; for(RG int e = ft[u]; e != -1; e = edge[e].nt){ RG int v = edge[e].to, f = edge[e].f + dis[u]; if(dis[v] > f){ dis[v] = f; if(vis[v]){ flag = 1; return; } Dfs(v); } } vis[u] = 0;}int main(){ mem(dis, 63); mem(ft, -1); n = Get(); m1 = Get(); m2 = Get(); for(RG int i = 1; i <= m1; i++){ RG int u = Get(), v = Get(), f = Get(); Add(u, v, f); } for(RG int i = 1; i <= m2; i++){ RG int u = Get(), v = Get(), f = Get(); Add(v, u, -f); } dis[1] = 0; Dfs(1); if(flag) printf("-1\n"); else if(dis[n] == dis[0]) printf("-2\n"); else printf("%d\n", abs(dis[n])); return 0;}