Submission #2672727

---

Source Code Expand

/// 8:43
#include <bits/stdc++.h>

using namespace std;

const int inf = 2e9, Nmax = 2e5 + 5;
typedef long long ll;

int n, m, i, x,y, c;
int d[Nmax], t[Nmax];
pair<int, pair<int,int> > edge[2*Nmax];
ll ans;

int boss(int x)
{
    if(x == t[x]) return x;
    return t[x] = boss(t[x]);
}

void unite(int x, int y)
{
    x = boss(x), y = boss(y);
    t[x] = y;
}

int main()
{
//    freopen("input", "r", stdin);
 //   freopen("output", "w", stdout);

    cin.sync_with_stdio(false);

    cin >> n >> m;
    for(i=0; i<n; ++i) d[i] = inf, t[i] = i;

    for(i=1; i<=m; ++i)
    {
        cin >> x >> y >> c;
        d[x] = min(d[x], c+1);
        d[y] = min(d[y], c+2);
        edge[i] = {c, {x, y}};
    }

    for(int j=0; j<2; ++j)
    {
        for(i=1; i<n; ++i)
            d[i] = min(d[i], d[i-1] + 2);
        d[0] = min(d[0], d[n-1] + 2);
    }

    for(i=0; i<n; ++i)
        edge[++m] = {d[i], {i, i+1}};

    sort(edge+1, edge+m+1);

    for(i=1; i<=m; ++i)
    {
        x = edge[i].second.first;
        y = edge[i].second.second;
        c = edge[i].first;

        if(boss(x) != boss(y))
            ans += c, unite(x, y);
    }

    cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result