test/graph/bellman_ford.test.cpp

• View this file on GitHub
• Last update: 2026-07-17 10:26:14+00:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_B

Depends on

• graph/bellman_ford.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_B"

#include "graph/bellman_ford.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, M, S;
    std::cin >> N >> M >> S;
    constexpr auto inf = std::numeric_limits<int>::max() / 2;
    std::vector<std::tuple<int, int, int>> edges(M);
    for (auto &[u, v, w] : edges) {
        std::cin >> u >> v >> w;
    }
    auto dist = bellman_ford(N, edges, S);
    for (auto i = 0; i < N; ++i) {
        if (dist[i] == -inf) {
            std::cout << "NEGATIVE CYCLE\n";
            return 0;
        }
    }
    for (auto i = 0; i < N; ++i) {
        if (dist[i] == inf) {
            std::cout << "INF\n";
        } else {
            std::cout << dist[i] << "\n";
        }
    }
}

#line 1 "test/graph/bellman_ford.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_B"

#line 1 "graph/bellman_ford.hpp"



#include <algorithm>
#include <limits>
#include <tuple>
#include <vector>

template <typename T, T inf = std::numeric_limits<T>::max() / 2>
std::vector<T> bellman_ford(int n, const std::vector<std::tuple<int, int, T>> &edges, int src) {
    std::vector<T> dist(n, inf);
    dist[src] = 0;
    for (auto i = 0; i < n; ++i) {
        for (auto [u, v, w] : edges) {
            if (dist[u] < inf && dist[u] + w < dist[v]) {
                dist[v] = (i < n - 1) ? std::max(-inf, dist[u] + w) : -inf;
            }
        }
    }
    for (auto i = 0; i < n; ++i) {
        for (auto [u, v, w] : edges) {
            if (dist[u] == -inf) {
                dist[v] = -inf;
            }
        }
    }
    return dist;
}


#line 4 "test/graph/bellman_ford.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, M, S;
    std::cin >> N >> M >> S;
    constexpr auto inf = std::numeric_limits<int>::max() / 2;
    std::vector<std::tuple<int, int, int>> edges(M);
    for (auto &[u, v, w] : edges) {
        std::cin >> u >> v >> w;
    }
    auto dist = bellman_ford(N, edges, S);
    for (auto i = 0; i < N; ++i) {
        if (dist[i] == -inf) {
            std::cout << "NEGATIVE CYCLE\n";
            return 0;
        }
    }
    for (auto i = 0; i < N; ++i) {
        if (dist[i] == inf) {
            std::cout << "INF\n";
        } else {
            std::cout << dist[i] << "\n";
        }
    }
}

Back to top page