中国人郵便配達問題 (from AOJ, DPL_2-B : Permutation/Path - Chinese Postman Problem)

DPL_2_B.py

# AC (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1843026#1)
# [方針]
# オイラー閉路を持つ --> 全ての頂点の次数が偶数である
# => 奇数次数の頂点に対して、追加コストが最小になるように辺を追加する
V, E = map(int, raw_input().split())
 
INF = 10**9
e = [[INF]*V for i in xrange(V)]
deg = [0] * V
su = 0
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    e[s][t] = e[t][s] = min(e[s][t], d)
    deg[s] += 1
    deg[t] += 1
    su += d
odd = [v for v in xrange(V) if deg[v]%2]
dp = {}
dp[2**len(odd) - 1] = 0
# Warshall–Floyd Algorithm
for k in xrange(V):
    for i in xrange(V):
        for j in xrange(V):
            e[i][j] = min(e[i][j], e[i][k] + e[k][j])
# 奇数次数の頂点に対して最小重みマッチング
def dfs(state):
    if state in dp:
        return dp[state]
    res = INF
    for i, u in enumerate(odd):
        if state & (1 << i):
            continue
        for j, v in enumerate(odd):
            if u==v or state & (1 << j) or e[u][v]==INF: continue
            res = min(res, dfs(state | (1 << i) | (1 << j)) + e[u][v])
    dp[state] = res
    return res
print dfs(0) + su