Overview

Starting from town \(1\), we find the shortest travel time to visit all towns at least once and return to town \(1\) at the end (or output -1 if impossible). Since \(N \le 15\), we solve this using shortest paths + bitDP (Traveling Salesman Problem type).

Analysis

Key Observations

• Since “you may pass through the same town or road any number of times,” the actual movement can go through towns any number of times along the way.
• Therefore, movement between any two towns can be replaced with the “shortest path” between them.
  In other words, the optimal solution on the original graph can be obtained by “constructing a complete graph using the shortest distances between all pairs of towns, and then finding the shortest tour that visits all vertices on this complete graph.”

Why a Naive Approach Doesn’t Work

• Exhaustively searching all possible orderings of town visits gives \(N!\) possibilities, and even for \(N=15\), \(15! \approx 1.3\times 10^{12}\), which is far too many.
• Additionally, if we try to manage states including “which roads to take” on the original graph, the state space explodes.

Solution

1. Compute all-pairs shortest distances \(dist[u][v]\) using Floyd–Warshall
   
2. Find the minimum cost using bitDP with “visited set” represented as bits (the classic DP for the Traveling Salesman Problem)

Furthermore, if there exists even one town unreachable from town 1, then visiting all towns is impossible, so we can immediately output -1.

Algorithm

1. All-Pairs Shortest Distances (Floyd–Warshall)

• Initialize \(dist[i][j]\) as “the shortest travel time from town \(i\) to town \(j\).”
  • \(dist[i][i]=0\)
  • For existing roads, use their weights; otherwise, set to \(INF\)
• Update all pairs \((i,j)\) to their shortest distances using Floyd–Warshall.

As a result, for example, “even if there is no direct road from \(2 \rightarrow 5\), if \(2 \rightarrow 3 \rightarrow 5\) is the shortest, then \(dist[2][5]\) becomes that total.”
From this point on, we only need to “use \(dist\) for inter-town travel costs,” and we no longer need to worry about the details of intermediate routes.

2. bitDP (Visited Set DP)

• Let \(mask\) be the visited set (bit set). If bit \(j\) is 1, then town \(j\) has been visited.
• Define \(dp[mask][i]\) as follows:

The minimum time when starting from town 1 (index 0), having visited all towns in the set \(mask\), and currently being at town \(i\)

Initial state: - Only town 1 visited, currently at town 1: \(dp[1<<0][0]=0\)

Transitions: - From \(dp[mask][i]\), go to an unvisited town \(j\) - New set \(nmask = mask \,|\, (1<<j)\) - Update:
\(dp[nmask][j] = \min(dp[nmask][j],\ dp[mask][i] + dist[i][j])\)

Answer: - Let \(full = (1<<N)-1\) represent all towns visited, and add the cost of returning to town 1: [ \min_{i} \left( dp[full][i] + dist[i][0] \right) ] - If there are unreachable states along the way, or if the answer cannot be constructed, output -1.

Complexity

• Time complexity:
  
  • Floyd–Warshall: \(O(N^3)\)
    
  • bitDP: \(O(2^N \cdot N^2)\)
    Total: \(O(N^3 + 2^N N^2)\)
• Space complexity:
  
  • \(dist\): \(O(N^2)\)
    
  • \(dp\): \(O(2^N \cdot N)\)
    Total: \(O(N^2 + 2^N N)\)

(For \(N=15\), \(2^{15}\cdot 15^2 \approx 7.4\) million, which is more than fast enough)

Implementation Notes

• If there are vertices where the shortest distance remains \(INF\) (especially those unreachable from town 1), we can immediately output -1.

• There is at most one road between any pair of towns in the input, but taking the min as a precaution is safe.

• Initialize DP values to a sufficiently large INF, and skip states that have not been reached.

• Converting town numbers to 0-indexed (town 1 → 0) in the code works well with bitwise operations.

  Source Code

import sys

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

    INF = 10**18
    dist = [[INF] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0

    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it)
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w

    # Floyd-Warshall for all-pairs shortest paths
    for k in range(N):
        dk = dist[k]
        for i in range(N):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            nd_base = dik
            for j in range(N):
                nd = nd_base + dk[j]
                if nd < di[j]:
                    di[j] = nd

    # Must be able to reach every town from town 1
    for v in range(N):
        if dist[0][v] == INF:
            print(-1)
            return

    full = (1 << N) - 1
    dp = [[INF] * N for _ in range(1 << N)]
    dp[1][0] = 0

    for mask in range(1 << N):
        row = dp[mask]
        for i in range(N):
            cur = row[i]
            if cur == INF:
                continue
            di = dist[i]
            nmask_base = mask
            for j in range(N):
                if nmask_base & (1 << j):
                    continue
                nd = cur + di[j]
                nmask = nmask_base | (1 << j)
                if nd < dp[nmask][j]:
                    dp[nmask][j] = nd

    ans = INF
    for i in range(N):
        cost = dp[full][i] + dist[i][0]
        if cost < ans:
            ans = cost

    print(ans if ans < INF else -1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.