Submission

Score: 0

User: Shangbin

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

Submitted On: 2026-01-21 22:25:08

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>

const int maxm = 1e4 + 5, maxn = 105, inf = 1e9;
int n, m, x, y, c, min_dist = 0, sec_min_dist = inf;
vector<tuple<int, int, int>> graph;
vector<int> used;
int boss[maxn];

int findBoss(int c){
    if (boss[c] == c) return c;
    else {
        boss[c] = findBoss(boss[c]);
        return boss[c];
    }
}
void resetBoss(){
    for (int i = 1; i <= n; i++) boss[i] = i;
}
int main(){
    cin >> n >> m;
    resetBoss();
    for (int i = 0; i < m; i++){
        cin >> x >> y >> c;
        graph.push_back({c, x, y});
    }
    sort(graph.begin(), graph.end());
    for (int i = 0; i < m; i++){
        auto [w, x, y] = graph[i]; 
        int boss_x = findBoss(x), boss_y = findBoss(y);
        if (boss_x != boss_y){
            min_dist += w;
            boss[boss_y] = boss_x;
            used.push_back(i);
        }
    }
    cout << min_dist << ' ';
    for (auto u : used){
        resetBoss();
        min_dist = 0;
        for (int i = 0; i < m; i++){
            if (i == u) continue;
            auto [w, x, y] = graph[i]; 
            int boss_x = findBoss(x), boss_y = findBoss(y);
            if (boss_x != boss_y){
                min_dist += w;
                boss[boss_y] = boss_x;
            }
        }
        sec_min_dist = min(sec_min_dist, min_dist);
    }
    cout << sec_min_dist;
}