概要

この問題は、与えられた連結グラフのすべての辺を少なくとも1回通り、出発点に戻る最短経路（中国郵便配達問題）を求める問題です。

考察

グラフのすべての辺を少なくとも1回通る閉路（オイラー路）が存在するためには、すべての頂点の次数が偶数である必要があります（オイラー閉路の条件）。しかし、元のグラフには次数が奇数の頂点が存在する可能性があります。

次数が奇数の頂点がある場合、それらの頂点間を追加で移動する必要があります。つまり、元のグラフの辺の重みの総和に加えて、奇数次数の頂点間を最適にペアリングして移動するコストを追加する必要があります。

制約で「奇数次数の頂点の個数は16以下」とあるため、これらの頂点間の最短距離を事前計算し、bit DPを用いて最適なペアリングを求めることが効率的です。

アルゴリズム

1. グラフの構築: 入力からグラフを隣接リスト形式で構築します
2. 奇数次数頂点の抽出: 次数が奇数の頂点をリストアップします
3. 全点対最短距離の計算: 奇数次数頂点間の最短距離をBFSで計算します
4. 最小重み完全マッチング: 奇数次数頂点をペアリングする最小コストをbit DPで計算します
5. 結果の計算: 元の辺の重み総和 + 最小マッチングコスト を出力します

具体的には: - 奇数次数頂点が0個の場合は、単に辺の重み総和を出力 - 奇数次数頂点がある場合は、それらを最適にペアリングする最小コストを求め、総和に加算

計算量

• 時間計算量: \(O(N + M + K^2 \cdot N + 2^K \cdot K^2)\)
  • \(K\): 奇数次数頂点数（最大16）
  • グラフ構築: \(O(N + M)\)
  • 全点対最短距離: \(O(K \cdot (N + M))\)
  • bit DP: \(O(2^K \cdot K^2)\)
• 空間計算量: \(O(N + M + 2^K + K^2)\)

実装のポイント

• 多重辺があるため、隣接リストでは各辺を両方向に登録

• 最短距離計算はBFS（ダイクストラではなく）で十分（重みが正だが、BFSでOK）

• bit DPでは状態をビットマスクで管理し、未ペアの頂点を順番にペアリング

• 巨大な数値（10^18）で初期化してオーバーフローを防止

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    edges = []
    graph = [[] for _ in range(n+1)]
    total = 0
    index = 2
    deg = [0] * (n+1)
    
    for i in range(m):
        u = int(data[index]); v = int(data[index+1]); w = int(data[index+2])
        index += 3
        edges.append((u, v, w))
        graph[u].append((v, w))
        graph[v].append((u, w))
        deg[u] += 1
        deg[v] += 1
        total += w
    
    odd_vertices = []
    for i in range(1, n+1):
        if deg[i] % 2 == 1:
            odd_vertices.append(i)
    
    k = len(odd_vertices)
    if k == 0:
        print(total)
        return
        
    dist = [[10**18] * k for _ in range(k)]
    
    for i in range(k):
        start = odd_vertices[i]
        d = [10**18] * (n+1)
        d[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v, w in graph[u]:
                if d[v] > d[u] + w:
                    d[v] = d[u] + w
                    q.append(v)
        for j in range(k):
            dist[i][j] = d[odd_vertices[j]]
    
    dp = [10**18] * (1 << k)
    dp[0] = 0
    
    for mask in range(1 << k):
        if dp[mask] == 10**18:
            continue
        i = 0
        while i < k:
            if mask & (1 << i):
                i += 1
                continue
            j = i + 1
            while j < k:
                if mask & (1 << j):
                    j += 1
                    continue
                new_mask = mask | (1 << i) | (1 << j)
                cost = dp[mask] + dist[i][j]
                if dp[new_mask] > cost:
                    dp[new_mask] = cost
                j += 1
            i += 1
    
    print(total + dp[(1 << k) - 1])

if __name__ == "__main__":
    main()

---

この解説は deepseekv3 によって生成されました。