test/graph/bellman_ford/aoj_grl_1_b.test.cpp

• View this file on GitHub
• Last update: 2023-12-12 23:23:17+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B

Depends on

• Bellman-Ford (src/graph/bellman_ford.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B

#include "src/graph/bellman_ford.hpp"

#include <iostream>

using namespace std;

int main() {
	int v, e, r;
	cin >> v >> e >> r;
	BellmanFord<int> bf(v);
	for (int i = 0; i < e; ++i) {
		int s, t, d;
		cin >> s >> t >> d;
		bf.add_edge(s, t, d);
	}
	bf.build(r);
	if (bf.has_negative_cycle()) cout << "NEGATIVE CYCLE" << endl;
	else {
		for (int i = 0; i < v; ++i) {
			if (bf.is_unreachable(i)) cout << "INF" << endl;
			else cout << bf.distance(i) << endl;
		}
	}

	return 0;
}

#line 1 "test/graph/bellman_ford/aoj_grl_1_b.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B

#line 1 "src/graph/bellman_ford.hpp"



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

template<class T>
class BellmanFord {
private:
	struct Edge {
		int from, to;
		T cost;

		Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
	};

	static constexpr T INF = std::numeric_limits<T>::max();

	int n, s{};
	std::vector<Edge> g;
	std::vector<T> cost;
	std::vector<int> prevv;
	bool negative_cycle_flag{};

public:
	BellmanFord(int n) : n(n), cost(n), prevv(n) {}

	void add_edge(int from, int to, T cost) { g.emplace_back(from, to, cost); }

	void build(int from) {
		s = from;
		cost.assign(n, INF);
		prevv.assign(n, -1);
		cost[s] = 0;
		for (int i = 0; i < n; ++i) {
			for (Edge &e : g) {
				if (cost[e.from] == INF) continue;
				if (cost[e.to] > cost[e.from] + e.cost) {
					cost[e.to] = cost[e.from] + e.cost;
					prevv[e.to] = e.from;
					if (i == n - 1) {
						negative_cycle_flag = true;
						return;
					}
				}
			}
		}
	}

	T distance(int to) { return cost[to]; }

	std::vector<int> shortest_path(int to) {
		std::vector<int> path;
		for (int v = to; v != -1; v = prevv[v]) path.push_back(v);
		std::reverse(path.begin(), path.end());
		return path;
	}

	bool is_unreachable(int to) { return cost[to] == INF; }

	bool has_negative_cycle() { return negative_cycle_flag; }
};


#line 4 "test/graph/bellman_ford/aoj_grl_1_b.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int v, e, r;
	cin >> v >> e >> r;
	BellmanFord<int> bf(v);
	for (int i = 0; i < e; ++i) {
		int s, t, d;
		cin >> s >> t >> d;
		bf.add_edge(s, t, d);
	}
	bf.build(r);
	if (bf.has_negative_cycle()) cout << "NEGATIVE CYCLE" << endl;
	else {
		for (int i = 0; i < v; ++i) {
			if (bf.is_unreachable(i)) cout << "INF" << endl;
			else cout << bf.distance(i) << endl;
		}
	}

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	13 ms	7 MB
g++	00_sample_01.in	AC	13 ms	7 MB
g++	00_sample_02.in	AC	13 ms	7 MB
g++	01_small_00.in	AC	13 ms	7 MB
g++	01_small_01.in	AC	13 ms	7 MB
g++	02_corner_00.in	AC	12 ms	7 MB
g++	02_corner_01.in	AC	13 ms	7 MB
g++	02_corner_02.in	AC	12 ms	7 MB
g++	02_corner_03.in	AC	12 ms	7 MB
g++	02_corner_04.in	AC	13 ms	7 MB
g++	02_corner_05.in	AC	13 ms	7 MB
g++	02_corner_06.in	AC	13 ms	7 MB
g++	03_medium_00.in	AC	13 ms	7 MB
g++	03_medium_01.in	AC	13 ms	7 MB
g++	03_medium_02.in	AC	13 ms	7 MB
g++	03_medium_03.in	AC	13 ms	7 MB
g++	04_rand_00.in	AC	13 ms	7 MB
g++	04_rand_01.in	AC	13 ms	7 MB
g++	04_rand_02.in	AC	13 ms	7 MB
g++	04_rand_03.in	AC	14 ms	7 MB
g++	04_rand_04.in	AC	14 ms	7 MB
g++	04_rand_05.in	AC	14 ms	7 MB
g++	04_rand_06.in	AC	15 ms	7 MB
g++	04_rand_07.in	AC	15 ms	7 MB
g++	05_dag_00.in	AC	13 ms	7 MB
g++	05_dag_01.in	AC	13 ms	7 MB
g++	05_dag_02.in	AC	14 ms	7 MB
g++	05_dag_03.in	AC	14 ms	7 MB
g++	06_ring_00.in	AC	13 ms	7 MB
g++	06_ring_01.in	AC	13 ms	7 MB
g++	06_ring_02.in	AC	13 ms	7 MB
g++	06_ring_03.in	AC	13 ms	7 MB
g++	07_large_00.in	AC	14 ms	7 MB
g++	07_large_01.in	AC	16 ms	7 MB
g++	07_large_02.in	AC	14 ms	7 MB
g++	07_large_03.in	AC	15 ms	7 MB
g++	08_maximum_00.in	AC	18 ms	7 MB
g++	08_maximum_01.in	AC	32 ms	7 MB
g++	08_maximum_02.in	AC	28 ms	7 MB
g++	08_maximum_03.in	AC	37 ms	7 MB
clang++	00_sample_00.in	AC	12 ms	13 MB
clang++	00_sample_01.in	AC	11 ms	9 MB
clang++	00_sample_02.in	AC	11 ms	11 MB
clang++	01_small_00.in	AC	12 ms	13 MB
clang++	01_small_01.in	AC	12 ms	15 MB
clang++	02_corner_00.in	AC	12 ms	11 MB
clang++	02_corner_01.in	AC	12 ms	15 MB
clang++	02_corner_02.in	AC	11 ms	7 MB
clang++	02_corner_03.in	AC	12 ms	15 MB
clang++	02_corner_04.in	AC	12 ms	9 MB
clang++	02_corner_05.in	AC	13 ms	9 MB
clang++	02_corner_06.in	AC	12 ms	7 MB
clang++	03_medium_00.in	AC	12 ms	15 MB
clang++	03_medium_01.in	AC	12 ms	9 MB
clang++	03_medium_02.in	AC	12 ms	9 MB
clang++	03_medium_03.in	AC	12 ms	9 MB
clang++	04_rand_00.in	AC	12 ms	9 MB
clang++	04_rand_01.in	AC	12 ms	11 MB
clang++	04_rand_02.in	AC	12 ms	9 MB
clang++	04_rand_03.in	AC	13 ms	10 MB
clang++	04_rand_04.in	AC	13 ms	8 MB
clang++	04_rand_05.in	AC	13 ms	9 MB
clang++	04_rand_06.in	AC	14 ms	15 MB
clang++	04_rand_07.in	AC	14 ms	11 MB
clang++	05_dag_00.in	AC	13 ms	13 MB
clang++	05_dag_01.in	AC	12 ms	7 MB
clang++	05_dag_02.in	AC	12 ms	9 MB
clang++	05_dag_03.in	AC	13 ms	13 MB
clang++	06_ring_00.in	AC	13 ms	15 MB
clang++	06_ring_01.in	AC	12 ms	9 MB
clang++	06_ring_02.in	AC	12 ms	13 MB
clang++	06_ring_03.in	AC	13 ms	13 MB
clang++	07_large_00.in	AC	14 ms	11 MB
clang++	07_large_01.in	AC	15 ms	8 MB
clang++	07_large_02.in	AC	13 ms	9 MB
clang++	07_large_03.in	AC	14 ms	13 MB
clang++	08_maximum_00.in	AC	18 ms	12 MB
clang++	08_maximum_01.in	AC	31 ms	10 MB
clang++	08_maximum_02.in	AC	25 ms	13 MB
clang++	08_maximum_03.in	AC	35 ms	8 MB

Back to top page