test/graph/prim/aoj_grl_2_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/2/GRL_2_A

Depends on

• Prim (src/graph/prim.hpp)

Code

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

#include "src/graph/prim.hpp"

#include <iostream>

using namespace std;

int main() {
	int v, e;
	cin >> v >> e;
	Prim<int> p(v);
	for (int i = 0; i < e; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		p.add_edge(a, b, c);
	}
	cout << p.mst_cost() << endl;

	return 0;
}

#line 1 "test/graph/prim/aoj_grl_2_a.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A

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



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

template<class T>
class Prim {
private:
	int n;
	std::vector<std::vector<std::pair<int, T>>> g;

public:
	Prim(int n) : n(n), g(n) {}

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

	T mst_cost() {
		T cost = 0;
		std::vector<bool> used(g.size());
		std::priority_queue<std::pair<T, int>,
							std::vector<std::pair<T, int>>,
							std::greater<>>
			pq;
		pq.emplace(0, 0);
		while (!pq.empty()) {
			auto [now_cost, now_v] = pq.top();
			pq.pop();
			if (used[now_v]) continue;
			used[now_v] = true;
			cost += now_cost;
			for (auto [nv, nw] : g[now_v]) pq.emplace(nw, nv);
		}
		return cost;
	}
};


#line 4 "test/graph/prim/aoj_grl_2_a.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int v, e;
	cin >> v >> e;
	Prim<int> p(v);
	for (int i = 0; i < e; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		p.add_edge(a, b, c);
	}
	cout << p.mst_cost() << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample1.in	AC	13 ms	7 MB
g++	00_sample2.in	AC	13 ms	7 MB
g++	critical1.in	AC	12 ms	7 MB
g++	critical2.in	AC	27 ms	8 MB
g++	critical3.in	AC	183 ms	13 MB
g++	out1.in	AC	14 ms	7 MB
g++	out10.in	AC	217 ms	19 MB
g++	out11.in	AC	70 ms	11 MB
g++	out12.in	AC	108 ms	13 MB
g++	out13.in	AC	90 ms	12 MB
g++	out14.in	AC	107 ms	13 MB
g++	out15.in	AC	80 ms	11 MB
g++	out2.in	AC	13 ms	7 MB
g++	out3.in	AC	13 ms	7 MB
g++	out4.in	AC	12 ms	7 MB
g++	out5.in	AC	12 ms	7 MB
g++	out6.in	AC	215 ms	19 MB
g++	out7.in	AC	221 ms	19 MB
g++	out8.in	AC	218 ms	19 MB
g++	out9.in	AC	220 ms	19 MB
clang++	00_sample1.in	AC	12 ms	11 MB
clang++	00_sample2.in	AC	12 ms	11 MB
clang++	critical1.in	AC	12 ms	11 MB
clang++	critical2.in	AC	24 ms	14 MB
clang++	critical3.in	AC	140 ms	18 MB
clang++	out1.in	AC	12 ms	9 MB
clang++	out10.in	AC	171 ms	21 MB
clang++	out11.in	AC	57 ms	17 MB
clang++	out12.in	AC	87 ms	17 MB
clang++	out13.in	AC	73 ms	12 MB
clang++	out14.in	AC	82 ms	17 MB
clang++	out15.in	AC	64 ms	14 MB
clang++	out2.in	AC	12 ms	13 MB
clang++	out3.in	AC	11 ms	7 MB
clang++	out4.in	AC	12 ms	13 MB
clang++	out5.in	AC	13 ms	13 MB
clang++	out6.in	AC	174 ms	21 MB
clang++	out7.in	AC	172 ms	23 MB
clang++	out8.in	AC	174 ms	23 MB
clang++	out9.in	AC	172 ms	21 MB

Back to top page