POJ 3259 Wormholes（负权环路）

题意：

农夫约翰农场里发现了很多虫洞，他是个超级冒险迷，想利用虫洞回到过去，看再回来的时候能不能看到没有离开之前的自己，农场里有N块地，M条路连接着两块地，W个虫洞，连接两块地的路是双向的，而虫洞是单向的，去到虫洞之后时间会倒退T秒，如果能遇到离开之前的自己就输出YES，反之就是NO。

分析：

就是求一幅图中有没有负权环路， 可以bellman n-1次后再跑一次看看能不能更新， 能更新说明有环。

也可以spfa记录入队次数， 入队次数大于等于N说明有负权环路

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

#define rep(i,a,b) for(int i = a; i < b; i++)

#define _rep(i,a,b) for(int i = a; i <= b; i++)

using namespace std;

#define inf 0x3f3f3f3f

const int maxn = , maxm = ;

int N,M,W;

struct E

{

    int v, time, nxt;

}Edge[maxm];

int cnt = ;

int head[maxn], enter_cnt[maxn];

int dis[maxn], vis[maxn];

void add_edge(int u , int v, int d){

    Edge[cnt].v = v;

    Edge[cnt].time = d;

    Edge[cnt].nxt = head[u];

    head[u] = cnt++;

}

bool spfa(){

    fill(dis, dis+maxn, inf);

    memset(vis, , sizeof(vis));

    memset(enter_cnt, , sizeof(enter_cnt));

    queue<int> q;

    q.push();

    dis[] = ;

    vis[] = ;

    enter_cnt[]++;

    while(!q.empty()){

        int u = q.front();

        for(int i = head[u]; i != -; i = Edge[i].nxt){

            int v = Edge[i].v, d = Edge[i].time;

            if(dis[v] > dis[u] + d){

                if(++enter_cnt[v] >= N) return false; //如果入队次数 >= N， 那么一定有负权环路

                dis[v] = dis[u] + d;

                if(!vis[v]){

                    vis[v] = ;

                    q.push(v);

                }

            }

        }

        vis[u] = ;

        q.pop();

    }

    return true;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        memset(head, -, sizeof(head));

        cnt = ;

        scanf("%d %d %d", &N, &M, &W);

        for(int i = ; i < M; i++)

        {

            int tu,tv,tt;

            scanf("%d %d %d", &tu, &tv, &tt);

            add_edge(tu,tv,tt);

            add_edge(tv,tu,tt);

        }

        for(int i = ; i < W; i++)

        {

            int tu,tv,tt;

            scanf("%d %d %d", &tu, &tv, &tt);

            add_edge(tu,tv,-tt);

        }

        if(!spfa()) printf("YES\n");

        else printf("NO\n");

    }

}