Problem:
Chinese Postman Problem For a given weighted undirected graph G(V, E) , find the distance of the shortest route that meets the following criteria:  It is a closed cycle where it ends at the same point it starts.  The route must go through every edge at least once.  Input  |V|  |E|  s 0  t 0  d 0  s 1  t 1  d 1 : s |E|-1  t |E|-1  d |E|-1  , where |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V| -1 respectively.  s i and t i represent source and target verticess of i -th edge (undirected) and d i represents the distance between s i and t i (the i -th edge). Note that there can be multiple edges between a pair of vertices. Output Print the shortest distance in a line. Constraints  2 ≤ |V| ≤ 15  0 ≤ |E| ≤ 1,000  0 ≤ d i ≤ 1,000   s i ≠ t i  The graph is connected  Sample Input 1 4 4
0 1 1
0 2 2
1 3 3
2 3 4 Sample Output 1 10 Sample Input 2 4 5
0 1 1
0 2 2
1 3 3
2 3 4
1 2 5 Sample Output 2 18 Sample Input 3 2 3
0 1 1
0 1 2
0 1 3 Sample Output 3 7

Solution (Python):
def warshall_floyd(distance_table, point_size):
    for k in range(point_size):
        for i in range(point_size):
            for j in range(point_size):
                if distance_table[i][j] > distance_table[i][k] + distance_table[k][j]:
                    distance_table[i][j] = distance_table[i][k] + distance_table[k][j]

class bit:
    def __createtable():
        table = [None] * 64
        mask64 = (1 << 64) - 1
        hash = 0x03F566ED27179461
        for i in range(64):
            table[hash >> 58] = i
            hash = (hash << 1) & mask64
        return table
    
    __table = __createtable()

    def number_of_trailing_zeros(x):
        if x == 0:return 64
        mask64 = (1 << 64) - 1
        return bit.__table[((bit.lowest_one(x) * 0x03F566ED27179461) & mask64) >> 58]

    def lowest_one(i):
        return i & -i

def ccp(distance_table, point_size, v):
    if v:
        i = bit.number_of_trailing_zeros(v)
        v ^= (1 << i)
        return min(ccp(distance_table, point_size, v ^ (1 << j)) + distance_table[i][j] for j in range(point_size) if v & 1 << j)
    else:
        return 0


import sys
readline = sys.stdin.readline

point_size, e = map(int, readline().split())
distance_table = [[float('inf')] * point_size for _ in range(point_size)]
cost = 0
v = 0
for _ in range(e):
    s, t, d = map(int, readline().split())
    distance_table[s][t] = min(distance_table[s][t], d)
    distance_table[t][s] = min(distance_table[t][s], d)
    v ^= 1 << s ^ 1 << t
    cost += d

warshall_floyd(distance_table, point_size)
print(cost + ccp(distance_table, point_size, v))

Solution (Python):
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
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

Solution (Python):
def warshall_floyd(n, dists):
    prev = [t.copy() for t in dists]

    for k in range(n):
        current = [t.copy() for t in prev]
        prev_k = prev[k]
        for i in range(n):
            prev_i, current_i = prev[i], current[i]
            prev_i_k = prev_i[k]
            for j in range(n):
                current_i[j] = min(prev_i[j], prev_i_k + prev_k[j])
        prev = current

    return prev


def solve(n, links, total_d, odd_vertices):
    if not odd_vertices:
        return total_d

    d_table = warshall_floyd(n, links)
    d_table = [[d for oj, d in enumerate(d_table[oi]) if oj in odd_vertices] for ni, oi in enumerate(odd_vertices)]
    ndt = len(d_table)
    bit_dict = {1 << i: i for i in range(ndt)}

    def minimum_pair(remains):
        if not remains:
            return 0
        b = remains & -remains
        remains ^= b
        i = bit_dict[b]
        return min(minimum_pair(remains ^ (1 << j)) + d_table[i][j] for j in range(ndt) if remains & (1 << j))

    return total_d + minimum_pair((1 << ndt) - 1)


v, e = map(int, input().split())

dists = [[float('inf')] * v for _ in range(v)]
for i in range(v):
    dists[i][i] = 0
odd_vertices = [0] * v
total_d = 0

for _ in range(e):
    s, t, d = map(int, input().split())
    dists[s][t] = min(dists[s][t], d)
    dists[t][s] = min(dists[t][s], d)
    odd_vertices[s] ^= 1
    odd_vertices[t] ^= 1
    total_d += d

print(solve(v, dists, total_d, [i for i, v in enumerate(odd_vertices) if v]))

Solution (Python):
def warshall_floyd(n, dists):
    prev = [t.copy() for t in dists]

    for k in range(n):
        current = [[0] * n for _ in range(n)]
        prev_k = prev[k]
        for i in range(n):
            prev_i, current_i = prev[i], current[i]
            prev_i_k = prev_i[k]
            for j in range(n):
                current_i[j] = min(prev_i[j], prev_i_k + prev_k[j])
        prev = current

    return prev


def solve(n, links, total_d, odd_vertices):
    if not odd_vertices:
        return total_d

    d_table = warshall_floyd(n, links)
    d_table = [[d for oj, d in enumerate(d_table[oi]) if oj in odd_vertices] for ni, oi in enumerate(odd_vertices)]
    ndt = len(d_table)
    bit_dict = {1 << i: i for i in range(ndt)}

    def minimum_pair(remains):
        if not remains:
            return 0
        b = remains & -remains
        remains ^= b
        i = bit_dict[b]
        return min(minimum_pair(remains ^ (1 << j)) + d_table[i][j] for j in range(ndt) if remains & (1 << j))

    return total_d + minimum_pair((1 << ndt) - 1)


v, e = map(int, input().split())

dists = [[float('inf')] * v for _ in range(v)]
for i in range(v):
    dists[i][i] = 0
odd_vertices = [0] * v
total_d = 0

for _ in range(e):
    s, t, d = map(int, input().split())
    dists[s][t] = min(dists[s][t], d)
    dists[t][s] = min(dists[t][s], d)
    odd_vertices[s] ^= 1
    odd_vertices[t] ^= 1
    total_d += d

print(solve(v, dists, total_d, [i for i, v in enumerate(odd_vertices) if v]))

Solution (Python):
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())


no_edge = float("inf")

adj = [[no_edge] * V for i in range(V)]

for i in range(V):
    adj[i][i] = 0

odd_b = 0 

ans = 0


for l_i in f_i:
    s, t, d = map(int, l_i.split())
    t_d = min(d, adj[s][t])
    adj[s][t] = t_d
    adj[t][s] = t_d
    odd_b ^= 1 << s
    odd_b ^= 1 << t
    ans += d

if odd_b:
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
                
    
    mw = [no_edge] * (odd_b + 1)
    mw[0] = 0
    digits = len(bin(odd_b)) - 2

    for b in range(odd_b):
        for i in range(0, digits):
            if not (b & (1 << i)) and odd_b & (1 << i):
                for j in range(i + 1, digits):
                    if not (b & (1 << j)) and odd_b & (1 << j):
                        t_b = b + (1 << i) + (1 << j)
                        if t_b == t_b & odd_b:
                            t_w = mw[t_b]
                            mw[t_b] = min(t_w, mw[b] + adj[i][j])

    
    ans += mw[odd_b]
    print(ans)
else:
    print(ans)

Solution (Python):
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())


no_edge = 14001

adj = [[no_edge] * V for i in range(V)]

for i in range(V):
    adj[i][i] = 0

odd_b = 0 

ans = 0


for l_i in f_i:
    s, t, d = map(int, l_i.split())
    t_d = min(d, adj[s][t])
    adj[s][t] = t_d
    adj[t][s] = t_d
    odd_b ^= 1 << s
    odd_b ^= 1 << t
    ans += d

import math

if odd_b:
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
                
    
    mw = [no_edge] * (odd_b + 1)
    mw[0] = 0
    digits = int(math.log2(odd_b)) + 1

    for b in range(odd_b):
        for i in range(0, digits):
            if not (b & (1 << i)):
                for j in range(i + 1, digits):
                    if not (b & (1 << j)):
                        t_b = b + (1 << i) + (1 << j)
                        if t_b == t_b & odd_b:
                            t_w = mw[t_b]
                            mw[t_b] = min(t_w, mw[b] + adj[i][j])

    
    ans += mw[odd_b]
    print(ans)
else:
    print(ans)

Solution (Python):



"""Chinese Postman Problem."""

import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())


no_edge = 14001

adj = [[no_edge] * V for i in range(V)]

for i in range(V):
    adj[i][i] = 0

odd_b = 0 

ans = 0


for l_i in f_i:
    s, t, d = map(int, l_i.split())
    t_d = min(d, adj[s][t])
    adj[s][t] = t_d
    adj[t][s] = t_d
    odd_b ^= 1 << s
    odd_b ^= 1 << t
    ans += d


def odd_one(n):
    ans = 0
    while n:
        ans ^= (n & 1)
        n >>= 1
    return ans

import math

if odd_b:
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
                
    
    mw = [no_edge] * (odd_b + 1)
    mw[0] = 0
    digits = int(math.log2(odd_b)) + 1

    for b in range(odd_b):
        if odd_one(b):
            continue
        for i in range(0, digits):
            if not (b & (1 << i)):
                for j in range(i + 1, digits):
                    if not (b & (1 << j)):
                        t_b = b + (1 << i) + (1 << j)
                        if t_b == t_b & odd_b:
                            t_w = mw[t_b]
                            mw[t_b] = min(t_w, mw[b] + adj[i][j])

    
    ans += mw[odd_b]
    print(ans)
else:
    print(ans)

Solution (Python):
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())


no_edge = 14001

adj = [[no_edge] * V for i in range(V)]

for i in range(V):
    adj[i][i] = 0

odd_b = 0 

ans = 0


for l_i in f_i:
    s, t, d = map(int, l_i.split())
    t_d = min(d, adj[s][t])
    adj[s][t] = t_d
    adj[t][s] = t_d
    odd_b ^= 1 << s
    odd_b ^= 1 << t
    ans += d


def odd_one(n):
    ans = 0
    while n:
        ans ^= (n & 1)
        n >>= 1
    return ans

import math

if odd_b:
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
                
    
    mw = [no_edge] * (odd_b + 1)
    mw[0] = 0
    digits = int(math.log2(odd_b)) + 1

    for b, mw_b in enumerate(mw):
        if odd_one(b):
            continue
        for i in range(0, digits):
            if b & (1 << i):
                continue
            for j in range(i + 1, digits):
                if b & (1 << j):
                    continue
                t_b = b + (1 << i) + (1 << j)
                if t_b == t_b & odd_b:
                    t_w = mw[t_b]
                    mw[t_b] = min(t_w, mw_b + adj[i][j])

    
    ans += mw[odd_b]
    print(ans)
else:
    print(ans)

Solution (Python):
def warshall_floyd(n, dists):
    prev = [t.copy() for t in dists]

    for k in range(n):
        current = [t.copy() for t in prev]
        prev_k = prev[k]
        for i in range(n):
            prev_i, current_i = prev[i], current[i]
            prev_i_k = prev_i[k]
            for j in range(n):
                current_i[j] = min(prev_i[j], prev_i_k + prev_k[j])
        prev = current

    return prev


def solve(n, links, total_d, odd_vertices):
    if not odd_vertices:
        return total_d

    d_table = warshall_floyd(n, links)
    d_table = [[d for oj, d in enumerate(d_table[oi]) if oj in odd_vertices] for ni, oi in enumerate(odd_vertices)] 
    ndt = len(d_table)
    bit_dict = {1 << i: i for i in range(ndt)}

    def minimum_pair(remains):
        if not remains:
            return 0
        b = remains & -remains 
        remains ^= b 
        i = bit_dict[b] 
        return min(minimum_pair(remains ^ (1 << j)) + d_table[i][j] for j in range(ndt) if remains & (1 << j)) 

    return total_d + minimum_pair((1 << ndt) - 1)


v, e = map(int, input().split())

dists = [[float('inf')] * v for _ in range(v)]
for i in range(v):
    dists[i][i] = 0
odd_vertices = [0] * v
total_d = 0

for _ in range(e):
    s, t, d = map(int, input().split())
    dists[s][t] = min(dists[s][t], d)
    dists[t][s] = min(dists[t][s], d)
    odd_vertices[s] ^= 1
    odd_vertices[t] ^= 1
    total_d += d

print(solve(v, dists, total_d, [i for i, v in enumerate(odd_vertices) if v]))

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def resolve():
    V, E = iim()
    inf = float("inf")
    ad = [[inf]*V for i in range(V)]

    bi = [1<<i for i in range(V)]
    ans = 0
    odd = 0
    for i in range(E):
        s, t, d = iim()
        ad[s][t] = ad[t][s] = min(d, ad[s][t])

        odd ^= bi[s]
        odd ^= bi[t]
        ans += d

    if odd == 0:
        print(ans)
        return


    for _ in range(V):
        nochage = True
        for i in range(V):
            for j in range(i+1, V):
                for k in range(V):
                    d1 = ad[i][j]
                    d2 = ad[i][k] + ad[k][j]

                    if d1 > d2:
                        nochage = False
                        ad[i][j] = d2
                        ad[j][i] = d2
        if nochage:
            break

    v2 = [i for i in range(V) if odd & bi[i]]
    n2 = len(v2)
    dp = {0: 0}
    dk = [0]

    for i in range(n2):
        ii = bi[i]
        vi = v2[i]
        for j in range(i + 1, n2):
            jj = bi[j]
            vj = v2[j]

            for state in dk:
                ij = ii | jj
                if state & ij: continue

                st2 = state | ij
                co2 = dp[state] + ad[vi][vj]
                if st2 in dp:
                    if co2 < dp[st2]:
                        dp[st2] = co2
                else:
                    dp[st2] = co2
                    dk.append(st2)
    ans += dp[(1<<n2)-1]

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import math
import sys
from typing import List


def warshall_floyd(table: List[List[int]], vertex_num: int) -> None:
    for k in range(vertex_num):
        for i in range(vertex_num):
            for j in range(vertex_num):
                table[i][j] = min(table[i][j], table[i][k] + table[k][j])


if __name__ == "__main__":
    V, E = map(lambda x: int(x), input().split())
    adj = [[sys.maxsize] * V for i in range(V)]
    for i in range(V):
        adj[i][i] = 0

    odd_b = 0  
    ans = 0

    for _ in range(E):
        s, t, d = map(lambda x: int(x), input().split())
        min_d = min(d, adj[s][t])
        adj[s][t] = min_d
        adj[t][s] = min_d
        odd_b ^= 1 << s
        odd_b ^= 1 << t
        ans += d

    if odd_b:
        warshall_floyd(adj, V)

        
        mw = [sys.maxsize] * (odd_b + 1)
        mw[0] = 0
        digits = int(math.log2(odd_b)) + 1

        for b, mw_b in enumerate(mw):
            if 1 == b % 2:
                continue
            for i in range(0, digits):
                if b & (1 << i):
                    continue
                for j in range(i + 1, digits):
                    if b & (1 << j):
                        continue
                    t_b = b + (1 << i) + (1 << j)
                    if t_b == t_b & odd_b:
                        t_w = mw[t_b]
                        mw[t_b] = min(t_w, mw_b + adj[i][j])
        ans += mw[odd_b]
        print(ans)
    else:
        print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

INF = float('inf')

v, e = map(int, input().split())
adj = [[INF]*v for _ in range(v)]
for i in range(v):
    adj[i][i] = 0
odd_vertices = [0]*v
total_d = 0

for _ in range(e):
    s, t, d = map(int, input().split())
    adj[s][t] = adj[t][s] = min(adj[s][t], d)
    odd_vertices[s] ^= 1
    odd_vertices[t] ^= 1
    total_d += d

def warshall():
    for k in range(v):
        for i in range(v):
            for j in range(v):
                if adj[i][k] != INF and adj[k][j] != INF:
                    adj[i][j] = min(adj[i][j],adj[i][k] + adj[k][j])
def solve():
    if sum(odd_vertices) == 0:
        return total_d
    else:
        warshall()
        odd = []
        for i in range(v):
            if odd_vertices[i] == 1:
                odd += [i]
        n = len(odd)
        dp = [INF]*(1<<n)
        dp[0] = 0
        for state in range(1<<n):
            for sp in range(n):
                if not((state>>sp) & 1):
                    for ep in range(n):
                        d = adj[odd[sp]][odd[ep]]
                        if sp != ep and not((state>>ep) & 1) and d != INF:
                            new_state = state|(1<<sp)|(1<<ep)
                            dp[new_state] = min(dp[new_state], dp[state]+d)

    return total_d + dp[-1]

print(solve())