G7 - MST-Prim

template< class type >
class MST_Prim {
	const int n;
	unordered_set<int> vis;
	type dis[maxn+1];
public:
	const int INF = numeric_limits<type>::max()>>1u;
	int ar[maxn+1][maxn+1] {};
	explicit MST_Prim(const int n): n(n) {
		for (int i = 1; i <= n; i++) fill(ar[i]+1, ar[i]+n+1, INF);
		for (int i = 1; i <= n; i++) ar[i][i] = 0;
	}
	type solve() {
		unordered_set< int >().swap(vis);
		for (int i = 1; i <= n; i++) vis.insert(i);
		fill(dis+1, dis+n+1, INF);
		dis[*vis.begin()] = 0;
		for (int k = 0, cur; k < n; k++) {
			cur = *vis.begin();
			for (const auto i : vis) if (dis[i] < dis[cur]) cur = i;
			if (dis[cur] == INF) return INF;
			vis.erase(cur);
			for (const auto i : vis) dis[i] = min(dis[i], ar[cur][i]);
		}
		return accumulate(dis+1, dis+n+1, (type)0);
	}
};