POJ3259（虫洞）

题目大意：给你一张图，先输入m条双向边（权值为正），再输入w条单向边（权值为负），判断是否有负环

题目思路：bellman-ford或者SPFA都行，我用的是SPFA（因为和POJ1860类似，就不加详细注释了）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
using namespace std;
#define gamma 0.5772156649015328606065120 //欧拉常数
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 1001000
#define maxn 300000
typedef long long LL;
typedef pair<int,int> PII;

int n;
struct Node
{
    int over;  ///终点
    int v;     ///权值
    int next;
} node[5500];
int n_cnt,l[505]; ///头节点
int vis[505],d[505],cnt[505];

void init()
{
    memset(l,-1,sizeof(l));
    memset(d,inf,sizeof(d));     ///到节点需要的花费
    memset(vis,0,sizeof(vis));   ///是否在队列中
    memset(cnt,0,sizeof(cnt));   ///判断有负环的标记（入队超过n次就有负环）n是题目所给节点数
    n_cnt=0;
}

void add(int &x,int &y,int &v)  
{
    node[n_cnt].over=y;
    node[n_cnt].v=v;
    node[n_cnt].next=l[x];
    l[x]=n_cnt++;
}

int SPFA()
{
    int i,j;
    queue<int>q;
    q.push(1);
    d[1]=0;
    while(!q.empty())
    {
        int i=q.front();
        q.pop();
        vis[i]=0;
        if(++cnt[i]>n) return 1;
        for(j=l[i]; j!=-1; j=node[j].next)
        {
            int pos=node[j].over;
            if(d[pos]>d[i]+node[j].v)
            {
                d[pos]=d[i]+node[j].v;
                if(!vis[pos])
                {
                    q.push(pos);
                    vis[pos]=1;
                }
            }
        }
    }

    return 0;
}

int main()
{
    int i,j,group,m,w,x,y,v;
    //freopen("lxx.txt","r",stdin);
    scanf("%d",&group);
    while(group--)
    {
        init();
        scanf("%d%d%d",&n,&m,&w);
        for(i=0; i<m; ++i)
        {
            scanf("%d%d%d",&x,&y,&v);
            add(x,y,v);
            add(y,x,v);
        }
        for(i=0; i<w; ++i)
        {
            scanf("%d%d%d",&x,&y,&v);
            v=-v;
            add(x,y,v);
        }
        if(SPFA())printf("YES
");
        else printf("NO
");
    }
    return 0;
}