poj3259,简单判断有无负环，spfa

英语能力差！百度的题意才读懂！就是一个判断有无负环的题。SPFA即可。，注意重边情况！！

#include<iostream>   //判断有无负环，spfa
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int mark[503];int a[503][503];int d[503];int num_in[503];
bool spfa(int n)
{
    queue<int>q;
    q.push(1);
     d[1]=0;
     num_in[1]++;            //统计入队次数
    while(!q.empty()) 
    {
        int cur=q.front();        
        q.pop();
        if(num_in[cur]>=n)return 1;   //大于n，结束，表示有负环
        mark[cur]=0;                  //出队
        for(int i=1;i<=n;i++)
        {
            if(a[cur][i]+d[cur]<d[i])  //能松弛的松弛
            {
                d[i]=a[cur][i]+d[cur];
                if(mark[i]==0)        //能松弛又不在队列中的要入队
                {
                  mark[i]=1;
                  if(num_in[i]>=n)return 1;//大于n，结束，表示有负环
                   q.push(i);
                  num_in[i]++;
                }
            }
        }
    }
    return 0;
}
int main()
{
    int num,n,m,w;
    scanf("%d",&num);
    while(num--)
    {
       scanf("%d%d%d",&n,&m,&w);
        memset(d,0x3f,sizeof(d));
        memset(a,0x3f,sizeof(a));
        memset(mark,0,sizeof(mark));
        memset(num_in,0,sizeof(num_in));
    int x,y;
    for(int i=0;i<m;i++)          //注意重边！
    {
        scanf("%d%d",&x,&y);
        int temp; scanf("%d",&temp);
        if(a[x][y]>temp)          
        {
                a[x][y]=temp;
                a[y][x]=a[x][y];
        }
    }
    for(int i=0;i<w;i++)
    {
        scanf("%d%d",&x,&y);
       int temp;scanf("%d",&temp);
        temp=-temp;
        if(a[x][y]>temp)
        {
            a[x][y]=temp;
        }
    }
    if(spfa(n))printf("YES
");
    else printf("NO
");
    }
    return 0;
}