Submission

[PPPPPP-SSS][PPPPPPPPPP-SSSSSSSSS]

Score: 0

User: fluke

Problemset: E.Kingdom

Language: cpp

Time: 0.187 second

Submitted On: 2025-03-01 14:44:33

#include <bits/stdc++.h>
#define ll long long 
#define f first 
#define s second
#define pii pair<int,int> 
#define emb emplace_back
#define em emplace
#define all(x) x.begin(),x.end()
#define pb push_back
#define DB cout<<"\n";system("pause");
using namespace std;

int find_root(int node , vector <int> &parent){
    if(parent[node] == node)return node;
    return parent[node] = find_root(parent[node] , parent);
}

int main(){
//ios::sync_with_stdio(false);cin.tie(0);
    ll n,m,k;
    ll cost = 0;

    cin>>n>>m>>k;
    vector <int> parent(n);
    vector <pair<ll,pii> > edge_list(m);

    for(int i=1 ; i<n ;i++)parent[i] = i;
    for(int i=0;i<m;i++){
        cin>>edge_list[i].s.f>>edge_list[i].s.s>>edge_list[i].f;
    }
    sort(all(edge_list) , greater <pair<ll,pii>>());
    
    int road_break = 0;
    ll more_k = 1e18;
    ll less_k = 1e18;
    
    for(auto x : edge_list){
        ll value = x.f;
        int a = x.s.f;
        int b = x.s.s;

        int A = find_root(a,parent);
        int B = find_root(b,parent);

        if(A == B){
            if(value >= k){
                more_k = min(more_k , value - k);
            }
            else {
                less_k = min(less_k , k - value);
                road_break++;
            }
        }
        else { // A != B
            if(value >= k){
                parent[A] = B;
                more_k = min(more_k , value - k);
            }
            else {
                parent[A] = B;
                cost += k-value;
                less_k = 0;
            }
        }
    }

    for(int i=0 ; i<n-1;i++){
        int A = find_root(i,parent);
        int B = find_root(i+1,parent);
        
        if(A!=B){
            parent[A] = B;
            cost += k;
            less_k = 0;
        }
    }

    if(less_k == 0 || more_k == 0){
        cout<<cost + road_break;
    }
    else if(less_k <= more_k){
        cout<<cost + less_k + road_break -1 ;
    }
    else {
        cout<<cost + more_k + road_break;
    }




}