概要

この問題は、グラフのすべての辺を少なくとも1回通り、出発点に戻ってくる最短経路を求める問題で、グラフ理論では「中国郵便配達問題（Route Inspection Problem）」として知られています。

考察

1. オイラー閉路と次数の関係

グラフのすべての辺をちょうど1回ずつ通って戻ってくる経路（オイラー閉路）が存在するための条件は、「すべての頂点の次数（つながっている辺の数）が偶数であること」です。

もし、すべての頂点の次数が偶数であれば、単にすべての辺の重みの合計が答えになります。しかし、次数が奇数の頂点（奇頂点）が存在する場合、そのままではオイラー閉路を作ることができません。

2. 奇頂点の解消

奇頂点がある場合、いくつかの辺を「2回通る」ことで、見かけ上の次数を偶数にする必要があります。 - 辺を2回通ることは、その2頂点間に「同じ重みの新しい辺を追加する」ことと同じです。 - グラフ全体の奇頂点の個数は必ず偶数個になります（握手補題）。 - 奇頂点を2個ずつペアにし、その間を最短経路で結ぶ（＝その経路上の辺をすべて2回通る）ことで、ペアになった頂点の次数はそれぞれ+1され、偶数になります。

したがって、この問題は「奇頂点同士をどのようにペアリングすれば、追加する経路の長さの合計を最小化できるか」という問題に帰着されます。

3. 制約の活用

問題文に「奇数次数の頂点の個数は 16 以下である」という非常に重要な制約があります。奇頂点の数を \(K\) とすると、 \(K \le 16\) です。この小ささを利用して、動的計画法（DP）で最適なペアリングを探索することが可能です。

アルゴリズム

1. 全辺の重みの合計を計算

まず、すべての辺を1回通るための基礎コストとして、全辺の重みの総和を計算します。

2. 奇頂点間の最短距離を求める

奇頂点 \(K\) 個のすべての組み合わせについて、その間の最短距離を求めます。 - 各奇頂点を始点として、ダイクストラ法を \(K\) 回実行します。 - これにより、\(K \times K\) の距離行列 dist_matrix を作成します。

3. ビットDPによる最小重み完全マッチング

奇頂点の集合を \(S\) としたとき、それらをペアリングする最小コストをビットDPで求めます。 - dp[mask] : 既にペアリングされた頂点の集合を mask（ビット列）としたときの、追加コストの最小値。 - 遷移: 1. まだ使われていない頂点 \(i\) を一つ選ぶ。 2. \(i\) とペアにする別の未所属頂点 \(j\) をすべて試す。 3. dp[mask | (1<<i) | (1<<j)] = min(..., dp[mask] + dist_matrix[i][j])

4. 最終的な答え

全辺の重みの総和 + dp[(1 << K) - 1] が答えとなります。

計算量

奇頂点の数を \(K\) (\(K \le 16\))、頂点数を \(N\)、辺数を \(M\) とします。

• 時間計算量: \(O(K(M \log N) + 2^K \cdot K)\)

  • ダイクストラ法を \(K\) 回実行: \(O(K \cdot M \log N)\)
  • ビットDP: 状態数 \(2^K\) に対し、各遷移で \(K\) 通りを試すため \(O(2^K \cdot K)\)
  • \(K \le 16\) なので、 \(2^{16} = 65536\) であり、十分に間に合います。

• 空間計算量: \(O(N + M + 2^K)\)

  • 隣接リスト、距離配列、DPテーブルの保持に必要なメモリです。

実装のポイント

• DPの高速化: mask に対して「まだ使われていない最も番号の小さい頂点」を一つ固定して、それとペアになる相手を探すだけで十分です。これにより、重複した組み合わせの探索を避けることができます。

• ダイクストラ法の打ち切り: ダイクストラ法を実行中、すべての奇頂点への最短距離が確定した時点で探索を終了すると、実行時間を短縮できます。

• 多重辺の扱い: 隣接リストにすべての辺を保持すれば、ダイクストラ法は通常通り動作します。

  ソースコード

import sys
from heapq import heappush, heappop

def solve():
    # Fast input reading
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not input_data:
        return
    
    # Map input data to integers
    data = list(map(int, input_data))
    N, M = data[0], data[1]
    
    # Adjacency list and degree count
    adj = [[] for _ in range(N + 1)]
    total_weight = 0
    degree = [0] * (N + 1)
    
    ptr = 2
    for _ in range(M):
        u, v, w = data[ptr], data[ptr+1], data[ptr+2]
        ptr += 3
        adj[u].append((v, w))
        adj[v].append((u, w))
        degree[u] += 1
        degree[v] += 1
        total_weight += w
        
    # Identify vertices with odd degrees
    odd_vertices = [i for i in range(1, N + 1) if degree[i] % 2 != 0]
    num_odd = len(odd_vertices)
    
    # If all degrees are even, an Eulerian circuit exists
    if num_odd == 0:
        sys.stdout.write(str(total_weight) + '\n')
        return

    # Map odd vertices for faster lookup
    is_odd = [False] * (N + 1)
    for v in odd_vertices:
        is_odd[v] = True
        
    # Pre-calculate shortest path distances between all pairs of odd vertices
    # num_odd is guaranteed to be even and <= 16
    dist_matrix = [[0] * num_odd for _ in range(num_odd)]
    heappush_func = heappush
    heappop_func = heappop
    INF = 10**18
    
    for i in range(num_odd - 1):
        start_node = odd_vertices[i]
        dists = [INF] * (N + 1)
        dists[start_node] = 0
        pq = [(0, start_node)]
        
        found_count = 0
        while pq:
            d, u = heappop_func(pq)
            if d > dists[u]:
                continue
            if is_odd[u]:
                found_count += 1
                # Dijkstra pops nodes in increasing order of distance.
                # Once we've popped all odd vertices, we have their shortest distances.
                if found_count == num_odd:
                    break
            
            # Optimization: use local reference for adj[u]
            adj_u = adj[u]
            for v, w in adj_u:
                new_dist = d + w
                if dists[v] > new_dist:
                    dists[v] = new_dist
                    heappush_func(pq, (new_dist, v))
        
        # Fill the distance matrix for all pairs involving odd_vertices[i]
        dist_i = dist_matrix[i]
        for j in range(i + 1, num_odd):
            dist_i[j] = dist_matrix[j][i] = dists[odd_vertices[j]]
    
    # Solve minimum weight perfect matching on odd vertices using bitmask DP
    full_mask = (1 << num_odd) - 1
    dp = [INF] * (1 << num_odd)
    dp[0] = 0
    
    for mask in range(full_mask):
        if dp[mask] == INF:
            continue
        
        # Pick the first vertex i not in the current matching mask
        i = 0
        while (mask >> i) & 1:
            i += 1
            
        mask_with_i = mask | (1 << i)
        dist_i = dist_matrix[i]
        dp_mask = dp[mask]
        
        # Try pairing vertex i with every other vertex j not in the mask
        for j in range(i + 1, num_odd):
            if not ((mask >> j) & 1):
                new_mask = mask_with_i | (1 << j)
                cost = dp_mask + dist_i[j]
                if dp[new_mask] > cost:
                    dp[new_mask] = cost
                    
    # The answer is the original total weight plus the cost of added paths
    sys.stdout.write(str(total_weight + dp[full_mask]) + '\n')

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。