概要

すべての道路（辺）を少なくとも1回通って交差点1に戻る最短時間を求める問題で、無向グラフの 中国人郵便配達問題（Chinese Postman Problem） の典型形（奇数次数頂点が少ない版）です。

考察

重要な気づき

• 「全ての辺を少なくとも1回通る閉路」の最小コストは、基本的に
  • まず全辺を1回ずつ通るコスト \(S=\sum W_i\)
  • そこに「追加で同じ道を何回か通る」コスト の合計になります。
• 無向グラフで 各頂点の次数がすべて偶数 なら、各辺をちょうど1回ずつ通って始点に戻る オイラー閉路 が存在します。
  よってこの場合、最小コストは追加分が不要で \(S\) です。

なぜ追加が必要か（奇数次数頂点）

• 次数が奇数の頂点があると、オイラー閉路は存在しません。
• オイラー閉路を作るには、どの頂点も偶数次数になるように「辺を重複して通る（＝辺を追加したのと同じ効果）」必要があります。
• 無向グラフでは、奇数次数頂点の個数は必ず偶数個になります。
  それらを ペアにして結ぶ経路 を追加で重複させると、ペアの両端の次数が1ずつ増えて偶数化できます。

素朴案がダメな理由

• 「どの道を何回通るか」「順番をどうするか」を直接探索すると、経路の組合せが爆発して \(N,M\le 10^5\) では不可能です。
• しかしこの問題では 奇数次数頂点の数が16以下 という強い制約があり、ここだけを小さく扱うことで解けます。

どう解決するか

1. 追加で重複させるのは「奇数次数頂点同士を結ぶ経路」だけでよい。
2. どのペアを組むのが最小かは、奇数次数頂点集合上の 最小重み完全マッチング（ただし \(k\le 16\) なので bit DP で可）に帰着できる。
3. ペアのコストは「元グラフ上での最短距離」なので、各奇数頂点からダイクストラで最短距離を求める。

アルゴリズム

1. 入力からグラフを作り、各頂点の次数 deg[v] と全辺重み和 \(S=\sum W_i\) を計算する。
2. 奇数次数頂点を列挙して odd とする（個数を \(k\) とする）。
   • \(k=0\) ならオイラー閉路が存在し、答えは \(S\)。
3. 各奇数頂点 \(odd[i]\) を始点にダイクストラ法を行い、他の奇数頂点 \(odd[j]\) への最短距離 dist_odd[i][j] を得る。
   • コードでは「奇数頂点への距離が全部確定したら打ち切る」ことで少し高速化しています。
4. 奇数頂点のペアリング最小コストを bit DP で求める。
   • dp[mask]：mask に含まれる奇数頂点をすでにペアにしたときの最小追加コスト
   • 遷移：mask でまだ使っていない最小の頂点 i を選び、別の未使用 j と組ませて $\( dp[mask \cup \{i,j\}] = \min\left(dp[mask \cup \{i,j\}],\ dp[mask] + dist\_odd[i][j]\right) \)$
5. 最終的な答えは $\( S + dp[(1<<k)-1] \)$ （追加で重複して通る部分の最小コストを足す）。

計算量

• 時間計算量:
  
  • ダイクストラ \(k\) 回：\(O\left(k \, M \log N\right)\)
    
  • bit DP：\(O\left(2^k \, k^2\right)\)（\(k\le 16\) なので十分小さい）
    よって全体で \(O\left(k M \log N + 2^k k^2\right)\)
• 空間計算量:
  
  • グラフ：\(O(N+M)\)
    
  • 距離行列：\(O(k^2)\)、DP：\(O(2^k)\)
    よって \(O(N+M+2^k)\)

実装のポイント

• 多重辺があっても、隣接リストにそのまま追加して問題ありません（次数計算も辺ごとに増やす）。

• ダイクストラでは、奇数頂点以外への距離は最終的に不要なので、
  「奇数頂点への距離が全て確定した時点で終了」すると高速化できます（コード中の rem）。

• bit DP では「未使用の最小 index i を固定して相手 j を探す」形にすると、同じペアリングを重複計算せずに済みます。

  ソースコード

import sys
import heapq

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)

    g = [[] for _ in range(N + 1)]
    deg = [0] * (N + 1)
    sum_w = 0

    for _ in range(M):
        u = next(it)
        v = next(it)
        w = next(it)
        g[u].append((v, w))
        g[v].append((u, w))
        deg[u] += 1
        deg[v] += 1
        sum_w += w

    odd = [i for i in range(1, N + 1) if deg[i] & 1]
    k = len(odd)
    if k == 0:
        print(sum_w)
        return

    idx_of = [-1] * (N + 1)
    for i, v in enumerate(odd):
        idx_of[v] = i

    INF = 10**30
    heappush = heapq.heappush
    heappop = heapq.heappop

    def dijkstra(s):
        dist = [INF] * (N + 1)
        dist[s] = 0
        pq = [(0, s)]
        res = [INF] * k
        rem = k
        while pq and rem:
            d, u = heappop(pq)
            if d != dist[u]:
                continue
            idx = idx_of[u]
            if idx != -1 and res[idx] == INF:
                res[idx] = d
                rem -= 1
                if rem == 0:
                    break
            for v, w in g[u]:
                nd = d + w
                if nd < dist[v]:
                    dist[v] = nd
                    heappush(pq, (nd, v))
        return res

    dist_odd = [[0] * k for _ in range(k)]
    for i, s in enumerate(odd):
        d = dijkstra(s)
        dist_odd[i] = d

    full = (1 << k) - 1
    dp = [INF] * (1 << k)
    dp[0] = 0

    for mask in range(1 << k):
        cur = dp[mask]
        if cur == INF or mask == full:
            continue
        i = 0
        while (mask >> i) & 1:
            i += 1
        bit_i = 1 << i
        for j in range(i + 1, k):
            if (mask >> j) & 1:
                continue
            nmask = mask | bit_i | (1 << j)
            val = cur + dist_odd[i][j]
            if val < dp[nmask]:
                dp[nmask] = val

    print(sum_w + dp[full])

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。