Submission #4419099

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

typedef long long ll;

const int maxn = 4e5 + 7;

using namespace std;

int n, q, cnt;
int d[maxn];
int fa[maxn];
struct edge {
	int x, y, z;
	inline int operator < (const edge &a) const {
		return z < a.z;
	}
} e[maxn];

inline int read()
{
	int X = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') X = X * 10 + ch - '0', ch = getchar();
	return X;
}

int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline ll kruskal()
{
	ll ans = 0;
	sort(e + 1, e + cnt + 1);
	for (int i = 1; i <= cnt; i++) {
		int x = find(e[i].x), y = find(e[i].y);
		if (x != y) fa[x] = y, ans += e[i].z;
	}
	return ans;
}

int main(void)
{
	cin >> n >> q;
	for (int i = 0; i < n; i++) fa[i] = i, d[i] = 2e9;
	while (q--) {
		int a = read(), b = read(), c = read();
		e[++cnt] = (edge){a, b, c};
		d[a] = min(d[a], c + 1);
		d[b] = min(d[b], c + 2);
	}
	int r = 0;
	for (int i = 1; i < n; i++) if (d[i] < d[r]) r = i;
	for (int i = r + 1; i < r + n; i++) d[i % n] = min(d[i % n], d[(i - 1) % n] + 2);
	for (int i = 0; i < n; i++) e[++cnt] = (edge){i, (i + 1) % n, d[i]};
	cout << kruskal() << endl;
	
	return 0;
}

Submission Info

Judge Result