Day 174-Q4 — 2026-10-10 | 無向グラフの郵便配達路（奇頂点の最小重み完全マッチングを「到達する状態だけ」の bit DP で）

📋 コピーimport sys
import heapq


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    eu = [0] * m
    ev = [0] * m
    ew = [0] * m
    adj = [[] for _ in range(n)]
    deg = [0] * n
    for i in range(m):
        u = int(data[2 + 3 * i]) - 1
        v = int(data[3 + 3 * i]) - 1
        c = int(data[4 + 3 * i])
        eu[i], ev[i], ew[i] = u, v, c
        adj[u].append((v, c, i))
        adj[v].append((u, c, i))
        deg[u] += 1
        deg[v] += 1
    odd = [v for v in range(n) if deg[v] % 2]
    k = len(odd)
    INF = float('inf')

    # 奇頂点ごとに Dijkstra（距離と、木をたどるための親の辺）
    dist = []
    pe = []
    for s in odd:
        d = [INF] * n
        par = [-1] * n
        d[s] = 0
        pq = [(0, s)]
        while pq:
            du, u = heapq.heappop(pq)
            if du > d[u]:
                continue
            for v, c, i in adj[u]:
                nd = du + c
                if nd < d[v]:
                    d[v] = nd
                    par[v] = i
                    heapq.heappush(pq, (nd, v))
        dist.append(d)
        pe.append(par)
    D = [[dist[a][odd[b]] for b in range(k)] for a in range(k)]

    # 奇頂点の最小重み完全マッチング: 未使用のうち最小番号の i を必ず誰かと組ませる。
    # 到達する mask は「下位が詰まった接頭辞＋上の数ビット」だけで、2^k よりずっと少ない
    full = (1 << k) - 1
    memo = {full: 0}
    choice = {}
    order = [0]                          # 0 から到達する mask を列挙（popcount の小さい順）
    seen = {0}
    for mask in order:
        if mask == full:
            continue
        rest = full ^ mask
        i = (rest & -rest).bit_length() - 1
        r = rest ^ (1 << i)
        while r:
            low = r & -r
            nm = mask | (1 << i) | low
            if nm not in seen:
                seen.add(nm)
                order.append(nm)
            r ^= low
    for mask in reversed(order):         # popcount の大きい順に確定
        if mask == full:
            continue
        rest = full ^ mask
        i = (rest & -rest).bit_length() - 1
        Di = D[i]
        best = INF
        bj = -1
        r = rest ^ (1 << i)
        while r:
            low = r & -r
            j = low.bit_length() - 1
            val = Di[j] + memo[mask | (1 << i) | low]
            if val < best:
                best = val
                bj = j
            r ^= low
        memo[mask] = best
        choice[mask] = bj

    total = sum(ew)
    extra = [0] * m                     # 各辺をもう何回通るか
    mask = 0
    while mask != full:
        rest = full ^ mask
        i = (rest & -rest).bit_length() - 1
        j = choice[mask]
        total += D[i][j]
        v = odd[j]                       # odd[i] からの最短路木を odd[j] からさかのぼる
        while v != odd[i]:
            e = pe[i][v]
            extra[e] += 1
            v = eu[e] if ev[e] == v else ev[e]
        mask |= (1 << i) | (1 << j)

    # Hierholzer（反復版）で頂点 1 から出る閉路を辺番号の列で
    g = [[] for _ in range(n)]
    cnt = []
    for i in range(m):
        c = 1 + extra[i]
        for _ in range(c):
            idx = len(cnt)
            cnt.append(i)
            g[eu[i]].append((ev[i], idx))
            g[ev[i]].append((eu[i], idx))
    used = [False] * len(cnt)
    ptr = [0] * n
    stack = [(0, -1)]
    route = []
    while stack:
        v, e = stack[-1]
        lst = g[v]
        while ptr[v] < len(lst) and used[lst[ptr[v]][1]]:
            ptr[v] += 1
        if ptr[v] == len(lst):
            stack.pop()
            if e >= 0:
                route.append(cnt[e] + 1)
        else:
            to, idx = lst[ptr[v]]
            used[idx] = True
            stack.append((to, idx))
    route.reverse()
    print(total)
    print(len(route))
    print(' '.join(map(str, route)))


main()