Submission

[PPPPPPPPPP][PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: fluke

Problemset: E.Kingdom

Language: cpp

Time: 0.246 second

Submitted On: 2025-03-01 15:40:43

#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,use_edge=0;
    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++; // break
            }
        }
        else { // A != B
            use_edge ++ ;
            if(value >= k){
                parent[A] = B;
                more_k = min(more_k , value - k);
            }
            else {
                parent[A] = B;
                cost += k-value; // change cost 
                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;
        }
    }*/

    //cout<<use_edge;
    if(use_edge != n-1){
        cost += (n-1-use_edge)*k; // build new road
        less_k = 0;
    }
    
    if(less_k == 0 || more_k == 0){
        cout<<cost + road_break;
    }
    else if(less_k <= more_k){
        cout<<cost + road_break + min(-1 + less_k ,k);
    }
    else {
        cout<<cost + min(more_k , k) + road_break;
    }




}