Submission

Score: 100

User: mantaggez

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-12 15:14:28

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using tup = tuple<int, int, int, int>;

const int nx = 105;
const int INF = 1e9;

int n, m, dsu[nx], d1 = INF, d2 = INF;
vector<tup> edge;
vector<int> bad;

int find(int x)
{
    if(dsu[x] == x) return x;
    dsu[x] = find(dsu[x]);
    return dsu[x];
}

int MST(int skip)
{
    int sum = 0, cnt = 0;
    iota(dsu, dsu + nx, 0);
    for(auto& [w, u, v, idx] : edge)
    {
        if(idx == skip) continue;
        
        int pu = find(u), pv = find(v);
        if(pu != pv)
        {
            dsu[pu] = pv;
            sum += w;
            cnt++;
            if(skip == -1) bad.push_back(idx);
        }
    }
    return (cnt == n - 1 ? sum : INF);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0;i<m;i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edge.push_back({w, u, v, i});
    }

    sort(edge.begin(), edge.end());

    d1 = MST(-1);
    for(auto& idx : bad) d2 = min(d2, MST(idx));
    
    cout << d1 << ' ' << d2 ;
    
    return 0;
}