POJ 3159 Candies（SPFA+栈）差分约束

题意：给出m给 x 与y的关系。当中y的糖数不能比x的多c个。即y-x <= c 最后求fly[n]最多能比so[1]
多多少糖？

差分约束问题，就是求1-n的最短路，队列实现spfa
会超时了，改为栈实现，就可以

有负环时，用栈比队列快

数组开小了，不报RE，报超时，我晕

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <queue>

#include <stack>

#include <algorithm>

const int N = 210;

const int maxn = 30100;

const int maxm = 200000;

#define FOR(i,a,b) for(int i=a;i<b;i++)

#define init(a) memset(a,0,sizeof(a))

#define MIN INT_MIN

#define MAX INT_MAX

#define LL long long

using namespace std;

int max(int a,int b){if(a>b)return a; else return b;}

int min(int a,int b){if(a<b)return a; else return b;}

const int INF=0x3f3f3f3f;

struct node

{

    int v,w;

    int next;

}edge[maxm];

int head[maxn];

bool vis[maxn];

int dis[maxn];

int cnt;

void add(int a,int b,int w)//加边

{

    edge[cnt].v=b;

    edge[cnt].w=w;

    edge[cnt].next=head[a];

    head[a]=cnt++;

}

void SPFA(int s,int n)

{

    //stack<int>stk;

    int stk[100000];

    int top = 0;

    //stk.push(s);

    stk[top++] = s;

    FOR(i,1,n+1)

    {dis[i] = INF;

    vis[i] = 0;

    }

    dis[s] = 0;

    vis[s] = 1;

    while(top!=0)

    {

        int u=stk[--top];

        //stk.pop();

        vis[u]=false;

        for(int i=head[u];i!=-1;i=edge[i].next)

        {

            int v=edge[i].v;

            if(dis[v]>dis[u]+edge[i].w)

            {

                dis[v]=dis[u]+edge[i].w;

                if(!vis[v])

                {

                    vis[v]=true;

                    stk[top++] = v;

                }

            }

        }

    }

}

void initt()

{

    cnt=0;

    memset(head,-1,sizeof(head));

}

int main()

{

    int n,m;

    int a,b,c;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        initt();

        while(m--)

        {

            scanf("%d%d%d",&a,&b,&c);

            add(a,b,c);

        }

        SPFA(1,n);

        printf("%d\n",dis[n]);

    }

    return 0;

}