Submission

[PPPPPPP-SS]

Score: 0

User: Jayss

Problemset: รัฐบาล

Language: cpp

Time: 0.009 second

Submitted On: 2025-04-19 20:32:09

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

const int N = 105;

struct Edge {
    int u, v, w;
    bool operator < (const Edge &rhs) const {
        return w < rhs.w;
    }
};

int pa[N], n, m;
vector<Edge> graph;
int find(int u) {
    if (pa[u] == u) return u;
    return pa[u] = find(pa[u]);
}

vector<int> dist;
void kruskal(Edge no) {
    for (int i = 1;i <= n;i++) pa[i] = i;
    int cpn = n;
    int sum = 0;
    for (Edge e : graph) {
        if (e.u == no.u && e.v == no.v && e.w == no.w) continue;
        int a = find(e.u), b = find(e.v);
        if (a == b) continue;
        pa[b] = a;
        sum += e.w;
        cpn--;
        if (cpn == 1) break;
    }
    if (cpn == 1) dist.push_back(sum);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    while (m--) {
        int u, v, w; cin >> u >> v >> w;
        graph.push_back({u, v, w});
    }
    sort(graph.begin(), graph.end());
    kruskal({-1, -1, -1});
    for (Edge e : graph) kruskal(e);
    sort(dist.begin(), dist.end());
    dist.resize(unique(dist.begin(), dist.end()) - dist.begin());
    cout << dist[0] << ' ' << dist[1];

    return 0;
}