spfa

int spfa(int s)
{
    for(int i=1 ;i<=n ;i++)
        dis[i]=INF ;
    dis[s]=0 ;
    memset(vis,0,sizeof(vis)) ;
    vis[s]=1 ;
    queue <int> q ;
    q.push(s) ;
    ct[s]++ ;
    while(!q.empty())
    {
        int u=q.front() ;
        q.pop() ;
        vis[u]=0 ;
        for(int i=head[u] ;i!=-1 ;i=e[i].nxt)
        {
            int tt=e[i].t ;
            if(dis[tt]>dis[u]+e[i].v)
            {
                dis[tt]=dis[u]+e[i].v ;
                if(!vis[tt])
                {
                    ct[tt]++ ;
                    if(ct[tt]>=n)return 0 ;
                    vis[tt]=1 ;
                    q.push(tt) ;
                }
            }
        }
    }
    return 1 ;
}