[USACO05DEC]布局

Link

又是一道差分约束新系统的裸题，直接上最短路就可以。
对于两个点之间的距离小于某个数，直接$Add(X, Y, Z)$就行。
对于两个点之间的距离大于等于某个数，直接$Add(Y, X, - Z)$就行。
但是这个题确实是有坑点的，就是这个图是有可能不连通的，因此你必须还得做一次判断，看这个图是否连通。
很简单，就是取一个新的节点0，然后把他和所有的节点连起来$Add(0, i, 0)$，然后$Spfa(0)$一次就可以了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>

using namespace std ;

typedef long long LL ;
const int MAXN = 100010 ;
const int MAXM = 100010 ;
const int Inf = 100000000 ;

int N, ML, MD, Tot, H[MAXN], Num[MAXN] ;
struct Node {
	int F, T, L, Next ;
}	E[MAXN << 1] ;

inline int Read() {
	int X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

inline void Add(int F, int T, int L) {
	E[++ Tot].F = F ; E[Tot].T = T ; E[Tot].L = L ;
	E[Tot].Next = H[F] ; H[F] = Tot ;
}

#define LS (Now << 1)
#define RS ((Now << 1) | 1)
#define Mid ((L + R) >> 1)
#define E_Mid ((E[Now].L + E[Now].R) >> 1)

struct TREE {
	int L, R, Sum, Tag ;
}	E[MAXN << 1] ;

inline void Push_Up(int Now) {
	
}

int D[MAXN] ; bool V[MAXN] ;
inline void Spfa(int S) {
	for (int i = 1 ; i <= N ; i ++) D[i] = Inf, V[i] = false, Num[i] = 0 ;
	D[S] = 0 ; V[S] = true ; queue <int> Q ; Q.push(S) ;
	while (! Q.empty()) {
		int Now = Q.front () ; V[Now] = false ; Q.pop() ;
		for (int i = H[Now] ; i ; i = E[i].Next)
			if (D[E[i].T] > D[Now] + E[i].L) {
				D[E[i].T] = D[Now] + E[i].L ;
				Num[E[i].T] = Num[Now] + 1 ;
				if (Num[E[i].T] >= N) {
					printf("-1") ; exit(0) ;
				}
				if (! V[E[i].T])
					V[E[i].T] = true, Q.push(E[i].T) ;
			}
	}
	for (int i = 1 ; i <= N ; i ++) 
		cout << E[i].F << " " << E[i].T << " " << E[i].Next << endl ;

}

int main() {
	N = Read() ; ML = Read() ; MD = Read() ;
	for (int i = 1 ; i <= N ; i ++)
		Add(0, i, 0) ;
	for (int i = 1 ; i <= ML ; i ++) {
		int A = Read(), B = Read(), C = Read() ;
		Add(A, B, C) ;
	}
	for (int i = 1 ; i <= MD ; i ++) {
		int A = Read(), B = Read(), C = Read() ;
		Add(B, A, - C) ;
	}
	Spfa(0) ; Spfa(1) ;

	if (D[N] == Inf) printf("-2") ;
	else printf("%d\n", D[N]) ;
	return 0 ;
}