题目要求判断负环 
一部分为双向边 一部分为单向边
我用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;   
}

• Re:这题有什么要注意的 总是WA，大牛帮帮忙　，，审审我的SPFA模板 (2298) ccnujing 2008-07-27 16:37:04