Submission #6359766

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#define itn int
#define reaD read
#define N 200001
using namespace std;

int n, Q, f[N], cnt, fa[N]; 
struct edge { int from, to, cost; bool operator < (const edge &p) const { return cost < p.cost; } } e[N << 2]; 

inline int read()
{
	int x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
	return x * w;
}

inline void adde(int u, int v, int w) { e[++cnt] = (edge) { u, v, w }; }

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

long long Kruscal()
{
	sort(e + 1, e + cnt + 1); 
	long long ans = 0; 
	for(int i = 1; i <= cnt; i++)
	{
		int u = find(e[i].from), v = find(e[i].to), w = e[i].cost; 
		if(u == v) continue; 
		fa[u] = v; ans += w; 
	}
	return ans; 
}

int main()
{
	n = read(); Q = read();
	for(int i = 1; i <= n; i++) fa[i] = i; 
	memset(f, 0x3f, sizeof(f)); 
	while(Q--)
	{
		int u = read() + 1, v = read() + 1, w = reaD();
		adde(u, v, w); 
		f[u] = min(f[u], w + 1); f[v] = min(f[v], w + 2); 
	}
	int pos = 1; 
	for(int i = 2; i <= n; i++) if(f[i] < f[pos]) pos = i; 
	for(int i = pos; i <= pos + n - 1; i++) f[i % n + 1] = min(f[i % n + 1], f[(i - 1) % n + 1] + 2); 
	for(int i = 1; i <= n; i++) adde(i, i % n + 1, f[i]);
	printf("%lld\n", Kruscal()); 
	return 0;
}

Submission Info

Judge Result