Chinese Postman Added Weight

Problem

Compute the minimum extra weight needed to make an undirected weighted graph Eulerian, as in the Chinese postman problem.

Find all odd-degree vertices, compute all-pairs shortest paths with Floyd-Warshall, and pair the odd vertices with minimum total distance using a bitmask DP. edges is a list of [u, v, weight] triples of a connected graph. Return the added weight, or -1 when the odd vertices cannot be paired.

Hint

Duplicating the edges of a minimum-weight perfect matching of the odd vertices balances every degree.

Test cases

case 1

in: [3,[[0,1,1],[1,2,2]]]

expected: 3

case 2

in: [3,[[0,1,1],[1,2,1],[2,0,1]]]

expected: 0

case 3

in: [4,[[0,1,1],[1,2,1],[2,3,1],[3,0,1]]]

expected: 0

case 4

in: [4,[[0,1,1],[1,2,1],[2,3,1],[3,0,1],[0,2,5]]]

expected: 2

case 5

in: [4,[[0,1,1],[0,2,1],[0,3,1]]]

expected: 3

Starter codePython

def chinese_postman_added_weight(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor