Submission

[P-SSSSSSSS][PPPPPPPPPP-SSSSSSSSS]

Score: 0

User: fluke

Problemset: E.Kingdom

Language: cpp

Time: 0.045 second

Submitted On: 2025-02-17 16:22:09

#include <bits/stdc++.h>
#define ll long long
#define f first 
#define s second 
#define pii pair<int,int>
#define DB cout<<"\n";system("pause");
using namespace std;

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

int main(){
ios::sync_with_stdio(false);cin.tie(0);
    int n,m,k;
    ll cheap = 1e9;
    ll money = 0;
    cin>>n>>m>>k;
    vector <pair<ll,pair<int,int> > > edge_list(m);
    vector <int> parent(n);

    for(int i=0;i<n;i++)parent[i] = i;
    for(int i=0;i<m;i++){
        int x,y;
        ll z;
        cin>>x>>y>>z;
        edge_list[i]={z,{x,y}};
    }
    sort(edge_list.begin(),edge_list.end(),greater <pair<ll,pair<int,int> > >());

    //for(auto x : parent)cout<<x<<" ";
    //DB

    for(int i=0;i<m;i++){
        int a = edge_list[i].s.f;
        int b = edge_list[i].s.s;
        ll weight = edge_list[i].f;

        if(weight >= k){
            int A = find_root(parent,a);
            int B = find_root(parent,b);
            
            if(A != B){
                cheap = min(cheap , weight);
                parent[A] = B;
            }
            
        }
        else{
            int A = find_root(parent,a);
            int B = find_root(parent,b);

            if(A != B){
                cheap = k;
                parent[A] = B;
                money += k-weight;
            }
            else {
                money++;
            }

        }

        //cout<<a<<" "<<b<<"\n";  
        //for(auto x : parent)cout<<x<<" ";
        //DB

    }

    for(int i=1;i<n;i++){
        int A = find_root(parent,i);
        int B = find_root(parent,i-1);

        if(A != B){
            cheap = k;
            money += k;
            parent[A] = B;
        }
    }

    if(cheap > k){
        money += cheap-k;
    }
    cout<<money;

}