poj3169-所谓的差分约束，但是感觉题目各种问题
题目很好理解，转换为差分约束也好理解。
关键是差分约束是要n+1个点，多一个v0，但是如果按照差分去做，肯定会wa，因为这样做以后，样例肯定都过不了，想想看，v0到其他点距离为0，所以到v1最短为0，v4最短为0，怎么求都得不到最后的27啊？？？？？
还有像vj>=vi(j >= i)这些约束不用加，这个好理解，证明题目中没给这一块的测试用例，数据弱没关系，但是如果你加上了，可能会报错。
discuss好多疑问，，但是无人解决，只能说这题目还是有争议的。
一个解释：
差分约束系统有两种方式可以求解，最短路和最长路。当我们把不等式整理成d[a]+w<=d[b]时，我们求最长路。整理成d[a]+w>=d[b]时，我们求最短路。当求最短路时，我们通常要把各点距离初始化为正无穷，求最短路，把各点距离逐渐减小，直到符合所有不等式。也就是开始各点不符合条件，后来通过减小变得符合了，所以一定是符合条件的最大值。既然是求最大值，并且是减小各点距离，也就是把各点由数轴的右侧向左侧拉，所以我们一定要选择一个最终在数轴最左侧的点，并初始化为0，把所有正无穷的点拉近到符合不等式。最长路同理。
一肚子疑问，虽然如此，但是还是对差分约束有了了解，就是给出一些不等式类似xj-xi<=wb 这样的，能够通过求最短路获得其中的一组解，这也是数学计算机化的一种表现吧。
无语。。。。。忘牛人指示，下面是没有按照差分约束概念做的，a了，但是感觉好不爽，疑问很多。。。
#include <stdio.h>#define maxN 1100#define inf 1000000000struct EDGE {int v, w, next;}edge[20 * maxN];int preEdge[maxN];int dis[maxN];int edgeNum;bool vis[maxN];int queue[20 * maxN];int cnt[maxN];int N;void Init(){for (int i = 1; i <= N; ++ i){dis[i] = inf;vis[i] = false;preEdge[i] = 0;cnt[i] = 0;}}bool spfa(){int head = 0, tail = 1;queue[0] = 1;dis[1] = 0;while (head < tail){int u = queue[head];vis[u] = true;int p = preEdge[u];while (p != 0){int v = edge[p].v;int w = edge[p].w;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;if (!vis[v]){vis[v] = true;queue[tail] = v;tail ++;}if (++ cnt[v] > N){return false;}}p = edge[p].next;}vis[u] = false;head ++;}return true;}void addEdge(int u, int v, int w){edge[edgeNum].v = v;edge[edgeNum].w = w;edge[edgeNum].next = preEdge[u];preEdge[u] = edgeNum ++;//edgeNum ++;}int main(){int ML, MD;while (scanf("%d%d%d", &N, &ML, &MD) != EOF){edgeNum = 1;int u, v, w;Init();for (int i = 0; i < ML; ++ i){scanf("%d%d%d", &u, &v, &w);addEdge(u, v, w);}for (int i = 0; i < MD; ++ i){scanf("%d%d%d", &u, &v, &w);addEdge(v, u, -w);}//for (int i = 2; i <= N; ++ i)//{//addEdge(i, 1, 0);//addEdge(i,i - 1, 0);//}if(!spfa())printf("-1\n");else if (dis[N] == inf){printf("-2\n");}elseprintf("%d\n", dis[N]);}return 0;}