差分约束
1.该题求的是最大值，也就是说求整条路径所有点的表达式上界的最小值，也就是说求每个点的最短路径，对于xi点的表达式来说，xi的表达式应该诸如xi<=xj+c类型，那么我们就可以考虑将题面信息的边权关系转变为表达式的类型。
2.因为奶牛按照编号顺序排列，并且可能在同一点上，表达式也就是i<=i+1，也即i<=i+1 +0,转换为加边函数即add(i+1,i,0)
3.对于两头奶牛，如果二者好感距离10，说明二者距离相减的绝对值小于等于10，为减少麻烦，我们可以默认b比a大，也就是当a>b时，我们选择调换二者位置 swap(a,b).
那么二者好感距离为10，变成xi的表达形式，也就是b<=a+10,对应的加边函数即add(a,b,10)
4.对于两头奶牛，如果二者厌恶距离10，也就是说二者距离相减的绝对值大于等于10，为减少麻烦，我们可以默认b比a大，也就是当a>b时，我们选择调换二者位置 swap(a,b).
那么二者厌恶距离为10，变成xi的表达形式，也就是a<=b-10，转换为加边函数即add(b,a,-10)
5.将所有边作为起点（相当于虚拟源点的思路),执行一遍SPFA，如果存在负环，说明存在矛盾，无法进行布局，输出-1
6.将1号点作为起点，走一遍SPFA，如果最后dist[n]==inf，说明N号点与1号点之间不存在任何大小限制关系，那么自然N号点到1号点的最大距离可以为无穷大，输出-2
7.如果最后dist[n]不等于inf，说明1号点与N号点之间存在距离大小限制关系，并且根据上述几点的分析，我们可以得到1号点到N号点的最大距离。
# 1.只要存在正环/负环, 说明不存在方案
# 2.该题求的是最大值，即求最短路径，即所有上界的最小值，得到的xi关系都是诸如 xi<=xj+c
from collections import deque
N = 1010
M = 10000+10000+1000+10
e = [0]*M
ne = [0]*M
h = [-1]*N
w = [0]*M
inf = float('inf')
idx = 0
def add(a,b,c):
global idx
e[idx] = b
ne[idx] = h[a]
w[idx] = c
h[a] = idx
idx+=1
def spfa(size):
global dist
dist = [inf]*N
st = [False]*N
cnt = [0]*N
q = deque()
for i in range(1,size+1):
q.append(i)
st[i] = True
dist[i] = 0
while(q):
t = q.popleft()
st[t] = False
i = h[t]
while(i!=-1):
j = e[i]
if dist[j]>dist[t]+w[i]:
dist[j] = dist[t]+w[i]
cnt[j] = cnt[t]+1
if cnt[j]>=n:
return True
if not st[j]:
st[j] = True
q.append(j)
i = ne[i]
return False
n,l,d = map(int,input().split())
for i in range(l):
a,b,c = map(int,input().split())
if a>b:a,b = b,a
add(a,b,c)
for i in range(d):
a,b,c = map(int,input().split())
if a>b:a,b = b,a
add(b,a,-c)
for i in range(1,n):
add(i+1,i,0)
aa = spfa(n)
if aa:
print(-1)
else:
spfa(1)
if dist[n]==inf:
print(-2)
else:
print(dist[n])
虚拟源点做法
# 1.只要存在正环/负环, 说明不存在方案
# 2.该题求的是最大值，即求最短路径，即所有上界的最小值，得到的xi关系都是诸如 xi<=xj+c
from collections import deque
N = 1010
M = 10000+10000+1000+10
e = [0]*M
ne = [0]*M
h = [-1]*N
w = [0]*M
inf = float('inf')
idx = 0
def add(a,b,c):
global idx
e[idx] = b
ne[idx] = h[a]
w[idx] = c
h[a] = idx
idx+=1
def spfa(x):
global dist
dist = [inf]*N
st = [False]*N
cnt = [0]*N
q = deque()
q.append(x)
st[x] = True
dist[x] = 0
while(q):
t = q.popleft()
st[t] = False
i = h[t]
while(i!=-1):
j = e[i]
if dist[j]>dist[t]+w[i]:
dist[j] = dist[t]+w[i]
cnt[j] = cnt[t]+1
if cnt[j]>=n+1:
return True
if not st[j]:
st[j] = True
q.append(j)
i = ne[i]
return False
n,l,d = map(int,input().split())
for i in range(l):
a,b,c = map(int,input().split())
if a>b:a,b = b,a
add(a,b,c)
for i in range(d):
a,b,c = map(int,input().split())
if a>b:a,b = b,a
add(b,a,-c)
for i in range(1,n):
add(i+1,i,0)
for i in range(1,n+1):
add(0,i,0) #虚拟源点
aa = spfa(0)
if aa:
print(-1)
else:
spfa(1)
if dist[n]==inf:
print(-2)
else:
print(dist[n])
