提出 #45711153

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE
#define debug(...) 3
#else
#include "debug.h"
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    int low = 1, high = -1;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        --a; --b;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    int mn = -1;
    for (int i = 0; i < n; i++) {
        vector<int> vv;
        for (auto [u, w] : g[i]) {
            vv.push_back(w);
        }
        if ((int) vv.size() > 1) {
            sort(vv.begin(), vv.end());
            if (mn == -1) {
                mn = vv[0] + vv[1];
            } else {
                mn = min(mn, vv[0] + vv[1]);
            }
        }
    }
    high = mn;
    auto Check = [&](int x) {
        if (mn < x) {
            return false;
        }
        vector<vector<int>> g2(n);
        for (int i = 0; i < n; i++) {
            for (auto [u, w] : g[i]) {
                if (w < x) {
                    g2[i].push_back(u);
                }
            }
        }
        vector<int> color(n, -1);
        function<void(int)> Dfs = [&](int v) {
            for (int u : g2[v]) {
                if (color[u] != -1) continue;
                color[u] = color[v] ^ 1;
                Dfs(u);
            }
        };
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                color[i] = 0;
                Dfs(i);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int u : g2[i]) {
                if (color[u] == color[i]) {
                    return false;
                }
            }
        }
        return true;
    };
    while (low < high) {
        int mid = (low + high + 1) / 2;
        if (Check(mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    cout << low << '\n';
    return 0;
}

提出情報

ジャッジ結果