この問題はいわゆる中国人郵便配達問題です。

解法として以下が知られています。 グラフのすべての辺を \(1\) 度ずつ通る閉路をオイラー路と言い、この問題では与えられたグラフの一部の辺を \(2\) 本に増やしてオイラー路が存在するオイラーグラフを得るようにします。そのために、増やした辺の重みが最小となる組合せを求めて、辺の重みの総和が答えとなる。

オイラーグラフであることと、連結ですべての頂点の次数が偶数であることは同値です。

一般のグラフでは次数が奇数の頂点を集めます。このとき、これは偶数個あります。 それらを \(2\) 頂点ずつ組み合わせて、その最短経路に辺を一本ずつ増やすという操作を行います。 こうすることでオイラーグラフになります。

この\(2\) 頂点ずつ組み合わせる方法のうち、増やす辺の重みの和を最小にするようなものを求めます。 これは重み付きマッチング問題に帰着されます。

奇数次頂点数を \(K\) とすると、これはbit DPなどを用いて時間計算量 \(\mathrm{O}(K^2 2^K)\) などで最小のマッチングを求めることができます。この問題では、制約より奇数次の頂点数は \(16\) 以下なので十分高速に計算できます。 また、重みを求めるパートではダイクストラ法などを用いて最短経路を時間計算量 \(\mathrm{O}(K(N+M)\log N)\) で求められます。

よって、全体で時間計算量 \(\mathrm{O}(K(N+M)\log N+2^K K^2)\) でこの問題を解くことができます。

余談: 重み付きマッチング問題はEdmondsのアルゴリズムで時間計算量 \(\mathrm{O}(K^3)\) などで解くことも可能です。

実装例C(++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    vector<int> deg(n);
    long long sum = 0;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        sum += w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
        deg[u]++, deg[v]++;
    }
    vector<int> ver;
    for (int i = 0; i < n; ++i)
        if (deg[i] & 1) ver.emplace_back(i);
    vector<vector<long long>> mat(ver.size(), vector<long long>(ver.size(), 1e18));
    for (int i = 0; i < (int)ver.size(); ++i) {
        const int v = ver[i];
        vector<long long> dist(n, 1e18);
        dist[v] = 0;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
        pq.emplace(0, v);
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (dist[u] < d) continue;
            for (auto [x, w] : g[u]) {
                if (d + w < dist[x]) {
                    dist[x] = d + w;
                    pq.emplace(dist[x], x);
                }
            }
        }
        for (int j = 0; j < (int)ver.size(); ++j) {
            mat[i][j] = dist[ver[j]];
        }
    }
    vector<long long> dp(1 << (int)ver.size(), 1e18);
    dp[0] = 0;
    for (int bit = 0; bit < 1 << (int)ver.size(); ++bit) {
        if (dp[bit] == (long long)1e18) continue;
        for (int i = 0; i < (int)ver.size(); ++i) {
            if ((bit >> i) & 1) continue;
            for (int j = i + 1; j < (int)ver.size(); ++j) {
                if ((bit >> j) & 1) continue;
                int nbit = bit | (1 << i) | (1 << j);
                dp[nbit] = min(dp[nbit], dp[bit] + mat[i][j]);
            }
        }
    }
    cout << sum + dp.back() << endl;
}