Candies POJ - 3159(差分约束+栈优化SPFA)

题目来源: Candies

题意

现在给n个小朋友分糖果，给出m条语句Ａ B C表示小朋友A认为给B的糖果不能比自己多C(可以等于C)，问小朋友N与小朋友1的糖果数量差最少是多少

思路

给出的m条语句表示的意思写成数学语言为给A的糖果数和给B的糖果数满足B-A<=C。这就变成了典型的差分约束系统，可以从点B到点A建立一条权值为c的有向边，最终要求的即为点N到点1的最短路。
这个题如果用队列spfa会超时，需要改成栈优化的spfa（学到了）。
同时需要反向建边 变成A到B有权值为C的边，求1到N的最短路。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
int n, m, dis[30005];
bool vis[30005];
struct node
{
    int to, next, w;
}e[150005];
int head[30005], cnt;
void ins(int x, int y, int w)
{
    e[++cnt] = { y, head[x], w };
    head[x] = cnt;
}
inline void spfa(int s)
{
    for (int i = 1; i <= n; ++i)
    {
        vis[i] = false;
        dis[i] = 0xffffff;
    }
    dis[s] = 0;
    vis[s] = true;
    std::stack<int>q;
    q.push(s);
    while (!q.empty())
    {
        int u = q.top(); q.pop();
        vis[u] = false;
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].to;
            int w = e[i].w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}
inline void init()
{
    memset(head, 0, sizeof(head));
    cnt = 0;
}
int main()
{
    int x, y, w;
    while (~scanf("%d%d", &n, &m))
    {
        init();
        for (int i = 1; i <= m; ++i)
        {
            scanf("%d%d%d", &x, &y, &w);
            ins(y, x, w);
        }
        spfa(1);
        printf("%d\n", dis[n]);
    }
    return 0;
}