F - Wormholes

题目大意：

农民约翰在农场散步的时候发现农场有大量的虫洞，这些虫洞是非常特别的因为它们都是单向通道，为了方便现在把约翰的农田划分成N快区域，M条道路，W的虫洞。

约翰是时空旅行的粉丝，他希望这样做，在一个区域开始，经过一些道路和虫洞然后回到他原来所在的位置，这样也许他就能见到他自己了。

穿越虫洞会回到以前。。。。。（穿越者约翰）

/////////////////////////////////////////////////////////////

很明显这是一个很扯淡的故事，不过为了出一道带负权值的题目也是难为了出题人，迪杰斯特拉算法不能处理带有负权值的问题，佛洛依德倒是可以，不过复杂度很明显太高，所以spfa是不错的选择，只需要判断出发点时间是否变小.

#include<algorithm>

#include<queue>

#include<stdio.h>

#include<string.h>

#include<vector>

#include<math.h>

using namespace std;

const int maxn = ;

const int oo = 0xfffffff;

struct node

{

    int y, time;

    node(int y, int t):y(y), time(t){}

};

vector<node> G[maxn];

int v[maxn];

int spfa(int s)

{

    queue<int> Q;

    Q.push(s);

    while(Q.size())

    {

        s = Q.front();Q.pop();

        int len = G[s].size();

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

        {

            node q = G[s][i];

            if(v[s]+q.time < v[q.y])

            {

                v[q.y] = v[s] + q.time;

                Q.push(q.y);

            }

        }

        if(v[] < )

            return ;

    }

    return ;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int N, M, W, i, a, b, c;

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

        for(i=; i<=N; i++)

        {

            v[i] = oo;

            G[i].clear();

        }

        v[] = ;

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

        {

            scanf("%d%d%d", &a, &b, &c);

            G[a].push_back(node(b, c));

            G[b].push_back(node(a, c));

        }

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

        {

            scanf("%d%d%d", &a, &b, &c);

            G[a].push_back(node(b, -c));

        }

        int ans = spfa();

        if(ans == )

            printf("YES\n");

        else

            printf("NO\n");

    }

    return ;

}