403. Chinese Postman (Route Inspection) Problem

A postman must walk every street (edge) of a connected undirected weighted graph with n vertices (0-indexed) and m edges (each u, v, weight) at least once and return to the starting vertex, minimizing total distance walked. Print that minimum total distance.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains three integers u v w, an undirected weighted edge. Output: Print a single integer - the minimum total distance to walk every edge at least once and return to the start.

1 <= n <= 10

This is a genuinely different, harder problem than simply finding an Eulerian PATH/circuit (which is just existence-checking) - here, when no Eulerian circuit exists, you must compute the MINIMUM EXTRA distance needed to effectively create one by duplicating some edges, requiring the more involved odd-vertex-pairing technique.

Find the minimum total distance a postman must walk to cover every street at least once and return to the start. Brute force: Try every possible walking route covering all edges directly and find the shortest one - this is combinatorially expensive to search exhaustively, when the odd-vertex-pairing technique directly computes the minimum extra distance needed. Optimised: A graph has an Eulerian circuit (walk every edge exactly once) if and only if EVERY vertex has even degree - when some vertices have odd degree, the minimum extra 'doubled' distance needed to fix this is exactly the minimum-weight perfect matching of odd-degree vertices using their shortest-path distances, since 'duplicating' the path between a matched pair effectively gives every vertex along it one more degree, evening things out.

Compute all-pairs shortest distances with Floyd-Warshall and collect the odd-degree vertices (there are always an even number of them). Then find a minimum weight perfect matching among just these vertices using a Held-Karp-style DP over subsets: dp[mask] is the minimum cost to pair up all vertices marked in mask, computed by picking the lowest-indexed unpaired vertex in mask, trying every possible partner, and recursing on the remaining subset. The answer is the sum of all original edge weights plus this minimum matching cost. This replaces exhaustive pairing enumeration (factorial in the odd-vertex count) with a subset DP that is only exponential in that count, a large improvement as the odd-vertex count grows. Time: O(n^3 + k^2 * 2^k) Space: O(n^2 + 2^k)

Since the postman only needs to duplicate edges to fix vertices with odd degree, try every possible way of duplicating extra edges (or walks between odd-degree vertices) so that every vertex ends up with even degree, compute the total distance (original edges plus duplicated ones) for each valid choice, and keep the minimum. This considers every way of making the graph Eulerian and is correct, but the number of ways to choose duplicated paths is exponential in the number of edges or odd vertices. Time: O(2^m) Space: O(n^2)

Compute all-pairs shortest distances with Floyd-Warshall, then identify the odd-degree vertices. Instead of considering arbitrary edge duplications, restrict the search to pairing up the odd-degree vertices with each other and duplicating the shortest path between each pair; try every possible way of pairing them up exhaustively and take the pairing with the minimum total added distance. Since there are typically far fewer odd vertices than edges, this is a real improvement, though checking every pairing is still combinatorially expensive as the odd-vertex count grows. Time: O(n^3 + k!) Space: O(n^2)

1. If EVERY vertex already has EVEN degree, the graph has an Eulerian circuit already, and the answer is simply the sum of ALL edge weights - no street needs walking twice. 2. Otherwise, find every ODD-DEGREE vertex (there's always an even number of them) and compute the shortest-path distance between EVERY pair of them (Floyd-Warshall is convenient since n is tiny). 3. The extra distance beyond the sum of all edges is the MINIMUM-WEIGHT way to pair up all odd vertices (using those shortest-path distances) - try every pairing since n is small enough.

Time: O(n³) for Floyd-Warshall (all-pairs shortest paths) plus O(2^k * k²) for finding the minimum-weight matching among k odd-degree vertices (feasible since n, and hence k, is tiny, up to 10). Space: O(n²), for the all-pairs shortest-distance matrix.

Test a graph where every vertex already has even degree (the answer is simply the sum of all edge weights, no doubling needed), and n at its upper bound of 10, which is small enough for brute-force pairing of odd-degree vertices.

Be ready to explain WHY there's always an EVEN number of odd-degree vertices in any graph (a fundamental graph theory fact - the handshake lemma) - this guarantees the odd vertices can always be perfectly paired up, with none left over.