uva 11478(差分约束系统)

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

struct my{
  int v;
  int next;
  int dist;
};

const int maxn=10000;
int adj[maxn];
int m,n;
my bian[maxn];
bool inq[maxn];
int cnt[maxn];
int d[maxn];
int fa;

void init(){
  memset(bian,-1,sizeof(bian));
  memset(adj,-1,sizeof(adj));
  fa=0;
}

void myinsert(int u,int v,int zhi){
     bian[++fa].v=v;
     bian[fa].dist=zhi;
     bian[fa].next=adj[u];
     adj[u]=fa;
}

bool spfa(){
     queue<int> q;
     for (int i=1;i<=n;i++) {
        inq[i]=false;
        d[i]=0;
        cnt[i]=0;
        q.push(i);
     }
     inq[1]=true;
     while(!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=false;
        for (int i=adj[u];i!=-1;i=bian[i].next){
            int v=bian[i].v;
            if(d[v]>d[u]+bian[i].dist){
                d[v]=d[u]+bian[i].dist;
                if(!inq[v]){
                    q.push(bian[i].v);
                    inq[bian[i].v]=true;
                    if(++cnt[bian[i].v]>n) return true;
                }
            }
        }
    }
    return false;
}

bool test(int x){
   bool tt;
   for (int i=1;i<=n;i++){
    for (int j=adj[i];j!=-1;j=bian[j].next){
        bian[j].dist-=x;
    }
   }
   tt=spfa();
    for (int i=1;i<=n;i++){
    for (int j=adj[i];j!=-1;j=bian[j].next){
        bian[j].dist+=x;
    }
   }
return tt;
}
int main(){
    int u,v,zhi;
    while(scanf("%d%d",&n,&m)!=EOF){
            init();
        int l=0,r=0;
        for (int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&zhi);
        myinsert(u,v,zhi);
        r=max(zhi,r);
        }
        if(!test(r)){
            printf("Infinite ");
            continue;
        }
        if(test(1)) {
                printf("No Solution ");
                continue;
        }
        int ans=1;
        while(l<=r)
        {
            int mid=l+((r-l)>>1);
            if(test(mid))
                r=mid-1;
            else
            {
                    l=mid+1;
                    ans=mid;
            }
        }
        printf("%d ",ans);
    }
return 0;
}