POJ 3169

• 差分约束问题转化为最短路
• 由最短路三角形关系得到dist[u] + w >= dist[v]->dist[v] <= dist[u] + w,则说明dist[]已经是源点到个点之间的距离了.w是u指向v这条有向边的权值.
• 将牛的关系表达为不等式,然后建图,

1. dist[j] - dist[i] <= k -> dist[j] <= dist[i] + k:i指向j的边,权值为k
2. dist[j] - dist[i] >= k -> dist[i] <= dist[j] + (-k): j指向i的边,权值为-k

• 1 和 n 点可以任意分开说明dist[] = 初始化最大值
• 能够一直松弛,即存在 负权环 说明不能排队

  #include <iostream>
  #include <string.h>
  #include <queue>
  using namespace std;
  const int maxn = 1005;
  int e[maxn][maxn];
  bool vis[maxn];
  int dist[maxn];
  int n,m1,m2;
  int cnt[maxn];
  
  int bellmanford() {
  	queue<int> que;
  	memset(vis,0,sizeof vis);
  	memset(dist,0x3f,sizeof dist);
  	dist[1] = 0; vis[1] = 1;
  	que.push(1);
  	while (!que.empty()) {
  		int cur = que.front(); que.pop();
  		vis[cur] = 0;
  		for (int i=1; i<=n; i++) {
  			if (dist[i] > dist[cur] + e[cur][i]) {
  				dist[i] = dist[cur] + e[cur][i];
  				if (!vis[i]) {
  					vis[i] = 1;
  					que.push(i);
  					if (++cnt[i] > n) return -1;
  				}
  			}
  		}
  	}
  	if (dist[n] == 0x3f3f3f3f) return -2;
  	return dist[n];
  }
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	memset(e,0x3f,sizeof e);
  	scanf("%d%d%d",&n,&m1,&m2);
  	int u,v,w;
  	for (int i=1; i<=m1; i++) {
  		scanf("%d%d%d",&u,&v,&w);
  		e[u][v] = w;
  	}
  	for (int i=1; i<=m2; i++) {
  		scanf("%d%d%d",&u,&v,&w);
  		e[v][u] = -w;
  	}
  	cout << bellmanford() << endl;
  	return 0;
  }