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

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

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

#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判断负环）

最新文章

热门文章