poj-1125-Stockbroker Grapevine spfa模闆

本模闆無判斷負環部分，

判斷負環方法記錄每個點壓隊列次數 若有一大于V則存在負環

#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
#include<cstring>
#define maxx 999999999
using namespace std;
struct edge{
  int x,y,dis,next;
}e[];
int head[],n,m,l1,dequeue[],v[];
void init()
{
   for(int i=;i<=n;i++)
    head[i] = -;
}
void add(int pre,int to,int dis)
{
   e[l1].x = pre;
   e[l1].y = to;
   e[l1].dis= dis;
   e[l1].next = head[pre];
   head[pre] = l1;
   l1++;
}
int spfa(int star)
{
    memset(dequeue,,sizeof(dequeue));
    for(int i=;i<=n;i++)
        v[i] = maxx;
    v[star]  =;
    queue<int>qu;
    qu.push(star);
    dequeue[star] = ;
    while(!qu.empty())
    {
       int qu1 = qu.front();
       qu.pop();
       for(int i = head[qu1];i!=-;i = e[i].next){
           if(v[e[i].y]>v[e[i].x]+e[i].dis){
               v[e[i].y] = v[e[i].x]+e[i].dis;
               if(!dequeue[e[i].y]){
                     qu.push(e[i].y);
                     dequeue[e[i].y] = ;
               }
           }
       }
         dequeue[qu1] = ;
    }
    int ss =-;
    for(int i=;i<=n;i++)
        if(v[i]>ss)ss = v[i];
    return ss;
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
       init();
       l1 = ;
       for(int i=;i<=n;i++)
       {
           int m;
           scanf("%d",&m);
           while(m--){
              int a,b;
              scanf("%d%d",&a,&b);
              add(i,a,b);
           }
       }
        int minn = maxx,minnx;
       for(int i=;i<=n;i++)
       {
          int s = spfa(i);
          if(s<minn){minn = s;minnx = i;}
       }
       if(minn == maxx)printf("disjoint\n");
       else printf("%d %d\n",minnx,minn);
    }
    return ;
}