Submission #4420252

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <cmath> 
#include <algorithm>
using namespace std; 
inline int gi() {
    register int data = 0, w = 1;
    register char ch = 0;
    while (!isdigit(ch) && ch != '-') ch = getchar(); 
    if (ch == '-') w = -1, ch = getchar(); 
    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); 
    return w * data; 
}
const int MAX_N = 2e5 + 5;
const int INF = 2e9; 
struct Edge { int u, v, w; } e[MAX_N << 1]; 
bool operator < (const Edge &l, const Edge &r) { return l.w < r.w; } 
int N, cnt, Q, ds[MAX_N]; 
int pa[MAX_N]; 
int getf(int x) { return x == pa[x] ? x : pa[x] = getf(pa[x]); }
long long ans = 0; 
int main () {
	N = gi(), Q = gi();
	for (int i = 1; i <= N; i++) ds[i] = INF; 
	while (Q--) { 
		int A = gi() + 1, B = gi() + 1, C = gi(); 
		e[++cnt] = (Edge){A, B, C};
		ds[A % N + 1] = min(ds[A % N + 1], C + 1); 
		ds[B % N + 1] = min(ds[B % N + 1], C + 2); 
	} 
	int pos = min_element(&ds[1], &ds[N + 1]) - ds; 
	for (int i = pos % N + 1, j = pos; i != pos; j = i, i = i % N + 1) ds[i] = min(ds[j] + 2, ds[i]); 
	for (int i = 2; i <= N; i++) e[++cnt] = (Edge){i - 1, i, ds[i]}; 
	e[++cnt] = (Edge){N, 1, ds[1]}; 
	sort(&e[1], &e[cnt + 1]);
	for (int i = 1; i <= N; i++) pa[i] = i; 
	for (int i = 1; i <= cnt; i++) {
		int u = getf(e[i].u), v = getf(e[i].v); 
		if (u == v) continue;
		ans += e[i].w, pa[u] = v; 
	} 
	printf("%lld\n", ans); 
    return 0; 
} 

Submission Info

Judge Result