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了，但是感觉好不爽，疑问很多。。。
[cpp]
#include <stdio.h>

#define maxN 1100
#define inf 1000000000

struct 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()) www.zzzyk.com
            printf("-1\n");
        else if (dis[N] == inf)
        {
            printf("-2\n");
        }
        else
            printf("%d\n", dis[N]);
    }
    return 0;
}
作者：zhang20072844

补充：软件开发 , C++ ,