Submission

[PPPP-SSSSS][-SSSSSSSSSSSSSSSSSSS]

Score: 0

User: fluke

Problemset: E.Kingdom

Language: cpp

Time: 0.122 second

Submitted On: 2025-03-01 12:44:20

#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);
    int n,m,k;
    int money = 0;
    cin>>n>>m>>k;
    vector <int> dis(n,-1);
    vector <pair<int,pii>> edge_list(m);
    vector <int> parent(n);
    for(int i=0 ;i<m;i++)cin>>edge_list[i].s.f>>edge_list[i].s.s>>edge_list[i].f;
    for(int i=1;i<n;i++)parent[i]=i;
    sort(all(edge_list),greater <pair<int,pii>>());

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

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

        if(A != B){
            parent[A] = B;
            dis[a] = max(dis[a] , value);
            dis[b] = max(dis[b] , value);
        }
        else if(value < k)money++;// ทุบ 1 บาท

        //cout<<money<<"\n";
        //for(auto x : dis)cout<<x<<" ";
        //DB 
        
    }

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

        if(A != B){// สร้าง k บาท
            parent[A] = B;
            dis[i] = max(dis[i] , k);
            dis[i+1] = max(dis[i+1] , k);
            money += k;
        }
        
    }

    for(int i=0;i<n;i++){// เปรี่ยน ราคา
        if(dis[i] < k)money += k-dis[i];
    }

    cout<<money;

}