> 题目要求判断负环 
> 一部分为双向边 一部分为单向边
> 我用SPFA做的
> 对每一个顶点ＳＰＦＡ
> 当某一个顶点入队 顶点数目次 ，说明图中有负环
> 否则　没有负环
> ，，
> 下面是我的SPFA模板，，按原理写的 
> 大家看看是不是写错了
> 
> //单源最短路径 Bellman-ford优化算法 spfa 
> #include<cstdio>
> using namespace std;
> const int maxver=1000;
> const int maxlen=6000000;//整个路径的最大值 
> const int maxe=maxver*maxver ;//边数的最大值 
> int vernum;//顶点数目 
> int enqued[maxver];//是否入队 
> int quest[maxver*maxver];//边数的最大值 作为队列 
> int quecnt[maxver];//顶点的入队次数 
> int map[maxver][maxver];
> int shortest[maxver];//最短路径值 
> int pathpre[maxver];//记录前驱 
> //
> int spfa(int s)
> {
>     int i,v;
>     int h,t;//队列指针 
>     for(i=0;i<vernum;i++){
>            shortest[i]=maxlen; pathpre[i]=-1; quecnt[i]=0;enqued[i]=0;
>     }  
>     h=t=0;
>     enqued[s]=1; quest[t++]=s;  quecnt[s]++;
>     shortest[s]=0;
>     do{
>         v=quest[h++]; h=h%maxe; enqued[v]=0;   
>         if(quecnt[v]==vernum) return 1; //有负环 沿v的前驱必可找到一个负环 
>         for(i=0;i<vernum;i++)
>             if(shortest[i]>shortest[v]+map[v][i]){
>                 shortest[i]=shortest[v]+map[v][i];
>                 pathpre[i]=v;
>                 if(!enqued[i]){
>                     quest[t++]=i;
>                      t=t%maxe;
>                     enqued[i]=1;  
>                     quecnt[i]++;
>                 }   
>             }          
>             
>     }while(h!=t);    
>     return 0;
> }
> //
> int main()
> {
>     int i,j;
>     int n,m,w,f,s,e,t;
>     int flag;
>     scanf("%d",&f);
>     while(f--)
>     {
>            scanf("%d%d%d",&n,&m,&w);
>            vernum=n;
>            for(i=0;i<vernum;i++)
>                 for(j=0;j<vernum;j++)
>                     map[i][j]=maxlen;
>            for(i=0;i<m;i++){
>                 scanf("%d%d%d",&s,&e,&t);
>                 map[s-1][e-1]=t;
>                 map[e-1][s-1]=t;   
>             } 
>             for(i=0;i<w;i++){
>                 scanf("%d%d%d",&s,&e,&t);
>                 t=-t;
>                 map[s-1][e-1]=t;   
>             }
>             for(i=0;i<vernum;i++){
>                 flag=spfa(i);
>                 if(flag==1) break;
>             }
>             if(flag==0) printf("NO\n");
>             else printf("YES\n");
>     }
>     return 0;   
> }