中国人郵便配達問題

int chinesePostman(const Graph &g) {
    static const Weight INF = std::numeric_limits<Weight>::max() / 8;
    Weight total = 0;
    int n = g.size();
    std::vector<int> odds;
    static Weight dist[17][17];
    for (int i = 0; i < n; ++i) {
        std::fill(dist[i], dist[i] + n, INF);
        for (auto &e : g[i]) {
            int s = e.src, d = e.dst;
            Weight w = e.weight;
            total += w;
            dist[s][d] = std::min(dist[s][d], w);
        }
        if (g[i].size() & 1) odds.push_back(i);
    }
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
    static Weight dp[1 << 17];
    int k = odds.size();
    std::fill(dp, dp + (1 << k), INF);
    dp[0] = 0;
    for (int S = 0; S < 1 << k; ++S)
        for (int i = 0; i < k; ++i)
            if (~S >> i & 1)
                for (int j = 0; j < i; j++)
                    if (~S >> j & 1)
                        dp[S | 1 << i | 1 << j] =
                            std::min(dp[S | 1 << i | 1 << j], dp[S] + dist[odds[i]][odds[j]]);
    return total / 2 + dp[(1 << k) - 1];
}