C++ Library for Competitive Programming
/*
* @title グラフ/Prim 法
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A
*/
#include <iostream>
#include <vector>
#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/prim.hpp"
int main() {
int v, e;
std::cin >> v >> e;
std::vector<std::vector<emthrm::Edge<long long>>> edge(v);
while (e--) {
int s, t, w;
std::cin >> s >> t >> w;
edge[s].emplace_back(s, t, w);
edge[t].emplace_back(t, s, w);
}
std::cout << emthrm::prim(edge) << '\n';
return 0;
}
#line 1 "test/graph/prim.test.cpp"
/*
* @title グラフ/Prim 法
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A
*/
#include <iostream>
#include <vector>
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/prim.hpp"
#include <functional>
#include <queue>
#line 7 "include/emthrm/graph/prim.hpp"
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 9 "include/emthrm/graph/prim.hpp"
namespace emthrm {
template <typename CostType>
CostType prim(const std::vector<std::vector<Edge<CostType>>>& graph,
const int root = 0) {
const int n = graph.size();
CostType res = 0;
std::vector<bool> is_visited(n, false);
is_visited[root] = true;
std::priority_queue<Edge<CostType>,
std::vector<Edge<CostType>>,
std::greater<Edge<CostType>>> que;
for (const Edge<CostType>& e : graph[root]) {
if (e.dst != root) que.emplace(e);
}
while (!que.empty()) {
const Edge<CostType> e1 = que.top();
que.pop();
if (is_visited[e1.dst]) continue;
is_visited[e1.dst] = true;
res += e1.cost;
for (const Edge<CostType>& e2 : graph[e1.dst]) {
if (!is_visited[e2.dst]) que.emplace(e2);
}
}
return res;
}
} // namespace emthrm
#line 12 "test/graph/prim.test.cpp"
int main() {
int v, e;
std::cin >> v >> e;
std::vector<std::vector<emthrm::Edge<long long>>> edge(v);
while (e--) {
int s, t, w;
std::cin >> s >> t >> w;
edge[s].emplace_back(s, t, w);
edge[t].emplace_back(t, s, w);
}
std::cout << emthrm::prim(edge) << '\n';
return 0;
}