概要

与えられた無向グラフのすべての辺を少なくとも1回通る閉路のうち、総コストが最小となるものを求めよ。これは中国郵便配達問題（Chinese Postman Problem）の一種である。

考察

この問題は、すべての辺をちょうど1回ずつ通るオイラー閉路を持つグラフであれば、単純にすべての辺の重みの和が答えとなる。しかし、一般のグラフでは奇数次数の頂点が存在し、オイラー閉路を持たないことがある。

オイラー閉路が存在する条件は「すべての頂点の次数が偶数であること」である。もし奇数次数の頂点があれば、いくつかの辺を追加してすべての頂点の次数を偶数にし、オイラー閉路を作ることができる。このとき、追加する辺のコストの合計を最小にしたい。

具体的には、奇数次数の頂点同士をペアにして、それらの最短距離を足すことでコストを最小化することができる。これは最小重み完全マッチング問題に帰着される。制約により奇数次数の頂点数は最大16個と少ないので、bitDPなどを用いて効率的に解ける。

アルゴリズム

1. まず、すべての辺の重みの合計 \(S\) を計算する。
2. 次に、各頂点の次数を数え、奇数次数の頂点を列挙する。
3. 奇数次数の頂点同士の間の最短距離を全点対最短経路（Dijkstra法を各奇数次数頂点に対して実行）で求める。
4. この距離をもとに、奇数次数の頂点の最小重み完全マッチングをbitDPで求める。
5. 最終的な答えは \(S + \text{マッチングのコスト}\) となる。

計算量

• 時間計算量: \(O(M \log N + k^2 2^k)\)
  
  • ただし \(k\) は奇数次数の頂点数（\(k \leq 16\)）
• 空間計算量: \(O(N + M + k^2 + 2^k)\)

実装のポイント

• 多重辺が存在する可能性があるため、隣接リストにはすべての辺を保持する。

• Dijkstra法はpriority queue（heapq）を使って高速化する。

• 奇数次数の頂点数が少ないので、bitDPによる全探索が可能。

• bitDPの遷移では、未選択の頂点のうち最もインデックスが小さいものを固定してペアを作るとうまく探索できる。

  ソースコード

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()

この解説は qwen3-coder-480b によって生成されました。