bzoj2330糖果

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2330

差分约束裸题。练习用spfa判正环（一个点入队超过n次）。

据说有1e5个点连成一条链的数据，使得0点从1到n加边会TLE，而从n到1加边就300ms。为什么？

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N=1e5+;

int n,m,head[N],xnt,dis[N],ct[N];

long long ans;

bool in[N];

struct Edge{

    int next,to,w;

    Edge(int n=,int t=,int w=):next(n),to(t),w(w) {}

}edge[N*];

bool spfa()

{

    queue<int> q;

    memset(dis,-,sizeof dis);

    q.push();in[]=;dis[]=;

    while(q.size())

    {

        int k=q.front();q.pop();in[k]=;

        for(int i=head[k],v;i;i=edge[i].next)

            if(dis[k]+edge[i].w>dis[v=edge[i].to])

            {

                if(++ct[v]>=n)return ;

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

                if(!in[v])q.push(v),in[v]=;

            }

    }

    return ;

}

int main()

{

    scanf("%d%d",&n,&m);int k,x,y;

    for(int i=n;i;i--)//

        edge[++xnt]=Edge(head[],i,),head[]=xnt;

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%d",&k,&x,&y);

        if(k==)

        {edge[++xnt]=Edge(head[x],y,);head[x]=xnt;

            edge[++xnt]=Edge(head[y],x,);head[y]=xnt;}

        if(k==){if(x==y){printf("-1");return ;}

                    edge[++xnt]=Edge(head[x],y,),head[x]=xnt;}

        if(k==)edge[++xnt]=Edge(head[y],x,),head[y]=xnt;

        if(k==){if(x==y){printf("-1");return ;}

                    edge[++xnt]=Edge(head[y],x,),head[y]=xnt;}

        if(k==)edge[++xnt]=Edge(head[x],y,),head[x]=xnt;

    }

    if(spfa())

    {

        printf("-1");return ;

    }

    for(int i=;i<=n;i++)ans+=dis[i];

    printf("%lld",ans);

    return ;

}