Submission #75973138

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<pair<int, long long>>> graph(N);
    vector<int> deg(N, 0);
    long long total_sum = 0;

    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
        deg[u]++;
        deg[v]++;
        total_sum += w;
    }

    // Collect odd-degree vertices
    vector<int> odd;
    for (int i = 0; i < N; ++i) {
        if (deg[i] % 2 == 1) odd.push_back(i);
    }

    // If no odd vertices, Eulerian circuit already exists
    if (odd.empty()) {
        cout << total_sum << '\n';
        return 0;
    }

    int K = (int)odd.size();
    // Compute all-pairs shortest paths among odd vertices
    vector<vector<long long>> dist(K, vector<long long>(K, INF));

    for (int i = 0; i < K; ++i) {
        int src = odd[i];
        vector<long long> d(N, INF);
        d[src] = 0;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
        pq.push({0, src});

        while (!pq.empty()) {
            auto [cd, u] = pq.top(); pq.pop();
            if (cd != d[u]) continue;
            for (auto [v, w] : graph[u]) {
                if (d[v] > cd + w) {
                    d[v] = cd + w;
                    pq.push({d[v], v});
                }
            }
        }

        for (int j = 0; j < K; ++j) {
            dist[i][j] = d[odd[j]];
        }
    }

    // DP for minimum weight perfect matching
    vector<long long> dp(1 << K, INF);
    dp[0] = 0;

    for (int mask = 0; mask < (1 << K); ++mask) {
        if (dp[mask] == INF) continue;
        // find first unset bit
        int i = 0;
        while (i < K && (mask & (1 << i))) ++i;
        if (i == K) continue;
        for (int j = i + 1; j < K; ++j) {
            if (!(mask & (1 << j))) {
                int nmask = mask | (1 << i) | (1 << j);
                long long cand = dp[mask] + dist[i][j];
                if (cand < dp[nmask]) dp[nmask] = cand;
            }
        }
    }

    long long ans = total_sum + dp[(1 << K) - 1];
    cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result