题目链接：http://poj.org/problem?id=3259

题目就是问你能否回到原点而且时间还倒回去了。题目中有些路中有单向的虫洞能让时间回到过去

所以只要将虫洞这条边的权值赋为负然后再判断有没有负环就行了。

#include <iostream>#include <cstring>using namespace std;const int inf = 10001;int f , n , m , w ,dis[1001] , counts;struct TnT {    int u , v , weight;}T[5200];void relax(int u , int v , int weight) {    if(dis[v] > dis[u] + weight)        dis[v] = dis[u] + weight;}bool bellman_ford() {    for(int i = 1 ; i < n ; i++) {        for(int j = 1 ; j <= counts ; j++) {            relax(T[j].u , T[j].v , T[j].weight);        }    }    bool flag = true;    for(int i = 1 ; i <= counts ; i++) {        if(dis[T[i].v] > dis[T[i].u] + T[i].weight) {            flag = false;            break;        }    }    return flag;}int main() {    cin >> f;    int s , e , t;    while(f--) {        cin >> n >> m >> w;        counts = 0;        memset(dis , inf , sizeof(dis));        for(int i = 1 ; i <= m ; i++) {            cin >> s >> e >> t;            T[++counts].u = s , T[counts].v = e , T[counts].weight = t;            T[++counts].u = e , T[counts].v = s , T[counts].weight = t;        }        for(int i = 1 ; i <= w ; i++) {            cin >> s >> e >> t;            T[++counts].u = s , T[counts].v = e , T[counts].weight = -t;        }        if(bellman_ford()) {            cout << "NO" << endl;        }        else {            cout << "YES" << endl;        }    }    return 0;}

poj 3259 Wormholes（bellman-ford判断负环）