poj3259 Wormholes（Bellman-Ford判断负圈）

https://vjudge.net/problem/POJ-3259

一开始理解错题意了，以为从A->B一定得走路，B->A一定得走虫洞。emmm其实回来的时候可以路和虫洞都可以走，只要最终结果满足就好。

发现了这一点，我终于愉快地把我的floyd从wa改到了tle~

正解：用bellman-ford判断有无负圈。

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<stack>

#define lson l, m, rt<<1

#define rson m+1, r, rt<<1|1

#define IO ios::sync_with_stdio(false);cin.tie(0);

#define INF 0x3f3f3f3f

typedef unsigned long long ll;

using namespace std;

int a[][], dist[];

int k, kase, n, m, w, s, e, t;

typedef struct{

    int from, to;

    int cost;

}Node;

Node node[];

int solve()

{

    memset(dist, , sizeof(dist));//可以检查出所有的负圈

    for(int i = ; i <= n; i++){

        for(int j = ; j < *m+w; j++){

            Node e = node[j];

            if(dist[e.to] > dist[e.from]+e.cost){

                dist[e.to] = dist[e.from]+e.cost;

                if(i == n) return ;

            }

        }

    }

    return ;

}

int main()

{

    scanf("%d", &kase);

    while(kase--){

        scanf("%d%d%d", &n, &m, &w);

        for(int i = ; i < *m; i++){

            scanf("%d%d%d", &s, &e, &t);//路是双向的

            node[i].from = s; node[i].to = e;

            node[i].cost = t;

            i++;

            node[i].from = e; node[i].to = s;

            node[i].cost = t;

        }

        for(int i = *m; i < *m+w; i++){

            scanf("%d%d%d", &s, &e, &t);//虫洞是单向的

            node[i].from = s; node[i].to = e;

            node[i].cost = -t;

        }

        if(solve()) cout << "YES" << endl;

        else cout << "NO" << endl;

    }

    return ;

}