Submission #4044424

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
    char ch = getchar();
    int x = 0, flag = 1;
    for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
    for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x * flag;
}
void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

const int Maxn = 200009;
int fa[Maxn];
int find(int u) { 
	return fa[u] != u ? fa[u] = find(fa[u]) : u; 
}

struct edge {
	int u, v;
	LL w;
	int operator < (const edge b) const {
		return w < b.w;
	}
};
vector <edge> s;
int n, q;
LL val[Maxn];

void init() {
	n = read(), q = read();
	rep (i, 1, n) fa[i] = i;
	rep (i, 0, n) val[i] = INT_MAX - n;
	rep (i, 1, q) {
		int u = read(), v = read(), w = read();
		s.push_back((edge){u % n, v % n, w});
		val[(u + 1) % n] = min(val[(u + 1) % n], w + 1ll);
		val[(v + 1) % n] = min(val[(v + 1) % n], w + 2ll);
	}
}

void solve() {
	rep (i, 1, n - 1) val[i] = min(val[i - 1] + 2, val[i]);
	val[0] = min(val[n - 1] + 2, val[0]);
	rep (i, 1, n - 1) val[i] = min(val[i - 1] + 2, val[i]);

	rep (i, 1, n - 1) s.push_back((edge){i - 1, i, val[i]});
	s.push_back((edge){n - 1, 0, val[0]});
	
	LL ans = 0;
	sort(s.begin(), s.end());
	rep (i, 0, s.size() - 1) {
		int x = find(s[i].u), y = find(s[i].v);
		if (x != y) {
			ans += s[i].w;
			fa[x] = y;
		}
	}
	cout << ans << endl;
}

int main() {
///	freopen("G.in", "r", stdin);
///	freopen("G.out", "w", stdout);

	init();
	solve();

#ifdef Qrsikno
    debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
    return 0;
}

Submission Info

Judge Result