Overview

This is a problem of finding the shortest time to traverse all roads (edges) at least once and return to intersection 1. It is a classic form of the Chinese Postman Problem on an undirected graph (the version where the number of odd-degree vertices is small).

Analysis

Key Observations

• The minimum cost of “a closed walk that traverses every edge at least once” is essentially:
  • The cost of traversing each edge exactly once: \(S=\sum W_i\)
  • Plus the cost of “traversing some edges additional times”
• In an undirected graph, if every vertex has even degree, there exists an Eulerian circuit that traverses each edge exactly once and returns to the starting point.
  In this case, no additional cost is needed, so the minimum cost is \(S\).

Why Additional Traversals Are Needed (Odd-Degree Vertices)

• If there are vertices with odd degree, no Eulerian circuit exists.
• To create an Eulerian circuit, we need to “traverse some edges multiple times (equivalent to adding duplicate edges)” so that every vertex has even degree.
• In an undirected graph, the number of odd-degree vertices is always even.
  By additionally duplicating paths that pair up these vertices, the degree of both endpoints of each pair increases by 1, making them even.

Why a Naive Approach Fails

• Directly searching over “how many times to traverse each road” and “in what order” causes a combinatorial explosion, making it infeasible for \(N,M\le 10^5\).
• However, in this problem there is a strong constraint that the number of odd-degree vertices is at most 16, which allows us to handle only this small part efficiently.

How to Solve It

1. The only paths we need to duplicate are “paths connecting pairs of odd-degree vertices.”
2. Finding which pairing minimizes the cost reduces to a minimum weight perfect matching on the set of odd-degree vertices (since \(k\le 16\), this can be solved with bitmask DP).
3. The cost of each pair is the “shortest distance on the original graph,” so we run Dijkstra from each odd-degree vertex.

Algorithm

1. Build the graph from input, compute each vertex’s degree deg[v] and the total edge weight sum \(S=\sum W_i\).
2. Enumerate odd-degree vertices into odd (let \(k\) be the count).
   • If \(k=0\), an Eulerian circuit exists and the answer is \(S\).
3. Run Dijkstra’s algorithm from each odd-degree vertex \(odd[i]\) to obtain the shortest distances dist_odd[i][j] to all other odd-degree vertices \(odd[j]\).
   • In the code, a small optimization is applied by terminating early once distances to all odd-degree vertices are determined.
4. Find the minimum cost pairing of odd-degree vertices using bitmask DP.
   • dp[mask]: the minimum additional cost when the odd-degree vertices included in mask have already been paired.
   • Transition: pick the smallest index i not yet used in mask, and pair it with another unused j: $\( dp[mask \cup \{i,j\}] = \min\left(dp[mask \cup \{i,j\}],\ dp[mask] + dist\_odd[i][j]\right) \)$
5. The final answer is $\( S + dp[(1<<k)-1] \)$ (add the minimum cost of the additional duplicate traversals).

Complexity

• Time complexity:
  
  • Dijkstra \(k\) times: \(O\left(k \, M \log N\right)\)
    
  • Bitmask DP: \(O\left(2^k \, k^2\right)\) (sufficiently small since \(k\le 16\))
    Overall: \(O\left(k M \log N + 2^k k^2\right)\)
• Space complexity:
  
  • Graph: \(O(N+M)\)
    
  • Distance matrix: \(O(k^2)\), DP: \(O(2^k)\)
    Overall: \(O(N+M+2^k)\)

Implementation Notes

• Multiple edges are handled correctly by simply adding them to the adjacency list as-is (degree is incremented per edge as well).

• In Dijkstra’s algorithm, distances to non-odd-degree vertices are ultimately unnecessary, so
  terminating early once “distances to all odd-degree vertices are determined” provides a speedup (the rem variable in the code).

• In the bitmask DP, by “fixing the smallest unused index i and searching for its partner j,” we avoid redundantly computing the same pairings.

  Source Code

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

---

This editorial was generated by gpt-5.2-high.