Overview

Given an undirected graph, find a closed walk that traverses every edge at least once with minimum total cost. This is a variant of the Chinese Postman Problem.

Analysis

If the graph has an Eulerian circuit—a closed walk that traverses every edge exactly once—then the answer is simply the sum of all edge weights. However, in a general graph, vertices with odd degree may exist, preventing an Eulerian circuit from existing.

The condition for an Eulerian circuit to exist is that “every vertex has even degree.” If there are vertices with odd degree, we can add some edges to make all vertex degrees even, thereby creating an Eulerian circuit. At this point, we want to minimize the total cost of the added edges.

Specifically, we can minimize the cost by pairing up the odd-degree vertices and adding the shortest distances between the paired vertices. This reduces to a minimum weight perfect matching problem. Due to the constraints, the number of odd-degree vertices is at most 16, which is small enough to solve efficiently using bitmask DP or similar techniques.

Algorithm

1. First, compute the sum \(S\) of all edge weights.
2. Next, count the degree of each vertex and enumerate the vertices with odd degree.
3. Compute the shortest distances between all pairs of odd-degree vertices using all-pairs shortest paths (running Dijkstra’s algorithm from each odd-degree vertex).
4. Based on these distances, find the minimum weight perfect matching of the odd-degree vertices using bitmask DP.
5. The final answer is \(S + \text{matching cost}\).

Complexity

• Time complexity: \(O(M \log N + k^2 2^k)\)
  
  • where \(k\) is the number of odd-degree vertices (\(k \leq 16\))
• Space complexity: \(O(N + M + k^2 + 2^k)\)

Implementation Notes

• Since multiple edges may exist between the same pair of vertices, the adjacency list should store all edges.

• Dijkstra’s algorithm should be sped up using a priority queue (heapq).

• Since the number of odd-degree vertices is small, exhaustive search via bitmask DP is feasible.

• In the bitmask DP transitions, fixing the unselected vertex with the smallest index and pairing it with another vertex allows for an effective search.

  Source Code

import sys
import heapq
from collections import defaultdict

def dijkstra(graph, start, n):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    edges = []
    graph = [[] for _ in range(N + 1)]
    
    for _ in range(M):
        u = int(data[idx])
        idx += 1
        v = int(data[idx])
        idx += 1
        w = int(data[idx])
        idx += 1
        edges.append((u, v, w))
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # Compute shortest distances from node 1
    dist_from_1 = dijkstra(graph, 1, N)
    
    # Find all nodes with odd degree
    degree = [0] * (N + 1)
    for u, v, w in edges:
        degree[u] += 1
        degree[v] += 1
    
    odd_nodes = [i for i in range(1, N + 1) if degree[i] % 2 == 1]
    
    # Total weight of all edges
    total_weight = sum(w for u, v, w in edges)
    
    # If all degrees are even, answer is total_weight
    if len(odd_nodes) == 0:
        print(total_weight)
        return
    
    # Build complete graph of odd nodes with shortest paths
    # We only need pairwise distances among odd nodes
    k = len(odd_nodes)
    
    # Run Dijkstra from each odd node to get distances to other odd nodes
    # Since k <= 16, we can do k Dijkstra runs which is acceptable
    odd_indices = {node: i for i, node in enumerate(odd_nodes)}
    dist_odd = [[float('inf')] * k for _ in range(k)]
    
    for i, node in enumerate(odd_nodes):
        dist_all = dijkstra(graph, node, N)
        for j, other in enumerate(odd_nodes):
            dist_odd[i][j] = dist_all[other]
    
    # Now solve minimum weight perfect matching on odd nodes
    # Using bit DP
    INF = float('inf')
    dp = [INF] * (1 << k)
    dp[0] = 0
    
    for mask in range(1 << k):
        if dp[mask] == INF:
            continue
        i = None
        for j in range(k):
            if not (mask & (1 << j)):
                i = j
                break
        if i is None:
            continue
        u_idx = i
        for v_idx in range(u_idx + 1, k):
            if not (mask & (1 << v_idx)):
                new_mask = mask | (1 << u_idx) | (1 << v_idx)
                cost = dist_odd[u_idx][v_idx]
                if dp[new_mask] > dp[mask] + cost:
                    dp[new_mask] = dp[mask] + cost
    
    min_match_cost = dp[(1 << k) - 1]
    result = total_weight + min_match_cost
    print(result)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.