test/graph/dijkstra/aoj_grl_1_a.test.cpp

• View this file on GitHub
• Last update: 2024-10-12 16:54:24+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_1_A

Depends on

• Dijkstra (src/graph/dijkstra.hpp)

Code

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

#include "src/graph/dijkstra.hpp"

#include <iostream>

using namespace std;

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

	return 0;
}

#line 1 "test/graph/dijkstra/aoj_grl_1_a.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_1_A

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



#include <algorithm>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

template<class T>
class Dijkstra {
private:
	static constexpr T INF = std::numeric_limits<T>::max();

	int s{};
	std::vector<std::vector<std::pair<int, T>>> g;
	std::vector<T> cost;
	std::vector<int> prevv;

public:
	Dijkstra(int n) : g(n), cost(n), prevv(n) {}

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

	void build(int from) {
		s = from;
		cost.assign(g.size(), INF);
		prevv.assign(g.size(), -1);
		std::priority_queue<std::pair<T, int>,
							std::vector<std::pair<T, int>>,
							std::greater<>>
			pq;
		cost[s] = 0;
		pq.emplace(0, s);
		while (!pq.empty()) {
			auto [now_cost, now_v] = pq.top();
			pq.pop();
			if (cost[now_v] < now_cost) continue;
			for (auto [nv, nw] : g[now_v]) {
				if (cost[nv] > cost[now_v] + nw) {
					cost[nv] = cost[now_v] + nw;
					prevv[nv] = now_v;
					pq.emplace(cost[nv], nv);
				}
			}
		}
	}

	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; }
};


#line 4 "test/graph/dijkstra/aoj_grl_1_a.test.cpp"

#include <iostream>

using namespace std;

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

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	239 ms	7 MB
g++	00_sample_01.in	AC	13 ms	7 MB
g++	01_small_00.in	AC	13 ms	7 MB
g++	01_small_01.in	AC	12 ms	7 MB
g++	02_medium_00.in	AC	13 ms	7 MB
g++	02_medium_01.in	AC	13 ms	7 MB
g++	03_corner_00.in	AC	12 ms	7 MB
g++	03_corner_01.in	AC	12 ms	7 MB
g++	03_corner_02.in	AC	12 ms	7 MB
g++	03_corner_03.in	AC	12 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	12 ms	7 MB
g++	04_rand_03.in	AC	13 ms	7 MB
g++	05_linear_00.in	AC	12 ms	7 MB
g++	05_linear_01.in	AC	12 ms	7 MB
g++	05_linear_02.in	AC	13 ms	7 MB
g++	05_linear_03.in	AC	13 ms	7 MB
g++	06_ring_00.in	AC	13 ms	7 MB
g++	06_ring_01.in	AC	12 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	13 ms	7 MB
g++	07_large_01.in	AC	15 ms	7 MB
g++	07_large_02.in	AC	18 ms	8 MB
g++	07_large_03.in	AC	20 ms	8 MB
g++	08_large_00.in	AC	34 ms	8 MB
g++	08_large_01.in	AC	38 ms	8 MB
g++	08_large_02.in	AC	47 ms	8 MB
g++	08_large_03.in	AC	61 ms	9 MB
g++	09_maximum_00.in	AC	269 ms	18 MB
g++	09_maximum_01.in	AC	598 ms	34 MB
g++	09_maximum_02.in	AC	206 ms	15 MB
g++	09_maximum_03.in	AC	349 ms	20 MB
clang++	00_sample_00.in	AC	12 ms	7 MB
clang++	00_sample_01.in	AC	11 ms	13 MB
clang++	01_small_00.in	AC	11 ms	9 MB
clang++	01_small_01.in	AC	12 ms	11 MB
clang++	02_medium_00.in	AC	12 ms	13 MB
clang++	02_medium_01.in	AC	12 ms	11 MB
clang++	03_corner_00.in	AC	12 ms	15 MB
clang++	03_corner_01.in	AC	12 ms	15 MB
clang++	03_corner_02.in	AC	11 ms	7 MB
clang++	03_corner_03.in	AC	12 ms	9 MB
clang++	04_rand_00.in	AC	11 ms	9 MB
clang++	04_rand_01.in	AC	11 ms	7 MB
clang++	04_rand_02.in	AC	12 ms	15 MB
clang++	04_rand_03.in	AC	12 ms	9 MB
clang++	05_linear_00.in	AC	11 ms	7 MB
clang++	05_linear_01.in	AC	11 ms	9 MB
clang++	05_linear_02.in	AC	12 ms	11 MB
clang++	05_linear_03.in	AC	12 ms	9 MB
clang++	06_ring_00.in	AC	11 ms	11 MB
clang++	06_ring_01.in	AC	11 ms	7 MB
clang++	06_ring_02.in	AC	12 ms	11 MB
clang++	06_ring_03.in	AC	12 ms	9 MB
clang++	07_large_00.in	AC	12 ms	13 MB
clang++	07_large_01.in	AC	14 ms	13 MB
clang++	07_large_02.in	AC	17 ms	14 MB
clang++	07_large_03.in	AC	19 ms	12 MB
clang++	08_large_00.in	AC	33 ms	12 MB
clang++	08_large_01.in	AC	37 ms	14 MB
clang++	08_large_02.in	AC	46 ms	17 MB
clang++	08_large_03.in	AC	59 ms	11 MB
clang++	09_maximum_00.in	AC	259 ms	21 MB
clang++	09_maximum_01.in	AC	579 ms	36 MB
clang++	09_maximum_02.in	AC	205 ms	17 MB
clang++	09_maximum_03.in	AC	336 ms	25 MB

Back to top page