Overview

This problem asks for the shortest route that visits all towns at least once and returns to the starting point (the Traveling Salesman Problem).

Analysis

• A route that visits all towns and returns to the start is allowed to pass through the same town or road multiple times, but directly enumerating all possible routes would result in an enormous computation (\(O(N!)\)).
• Since the graph is not a complete graph, direct roads do not necessarily exist between every pair of towns. Therefore, we first need to compute the shortest distances between all pairs of towns.
• Since the constraint is \(N \leq 15\), which is small, we can efficiently solve this using bitmask DP (dynamic programming). In bitmask DP, we maintain the set of visited towns and the current position as the state, and compute the minimum travel time.

Algorithm

1. Computing all-pairs shortest distances: Using the Floyd-Warshall algorithm, we compute the shortest travel time between all pairs of towns. This handles cases where travel is possible via detours even when no direct road exists.
2. Bitmask DP initialization:
   • Define dp[s][i] as the minimum travel time when the set of visited towns is s (a bitmask) and the current location is town i.
   • The initial state has only town 0 (the starting point) visited, so we set dp[1][0] = 0.
3. DP transitions:
   • From the current state (s, i), consider moving to a town j that has not yet been visited, and update with dp[ns][j] = min(dp[ns][j], dp[s][i] + dist[i][j]) (where ns = s | (1<<j)).
4. Computing the answer:
   • From the state where all towns have been visited (s = (1<<n)-1), consider the route returning to town 0, and compute min(dp[full][i] + dist[i][0]).

Complexity

• Time complexity: \(O(N^3 + 2^N \cdot N^2)\)
  • Floyd-Warshall algorithm: \(O(N^3)\)
  • Bitmask DP: number of states \(O(2^N \cdot N)\), transitions from each state \(O(N)\)
• Space complexity: \(O(2^N \cdot N)\)

Implementation Notes

• Before running the Floyd-Warshall algorithm, initialize self-loops (travel to the same town) to 0, and all other distances to a large value (INF).

• In the road input, multiple roads may exist between the same pair of towns, so only the minimum weight should be kept.

• When initializing the DP table, represent unreachable states with INF.

• After visiting all towns, it is necessary to check whether it is possible to return to town 0 (dist[i][0] != INF).

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0])
    m = int(data[1])
    INF = 10**18
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        
    index = 2
    for i in range(m):
        u = int(data[index]); v = int(data[index+1]); w = int(data[index+2])
        index += 3
        u -= 1
        v -= 1
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w
            
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    
    dp = [[INF] * n for _ in range(1<<n)]
    dp[1][0] = 0
    
    for s in range(1<<n):
        for i in range(n):
            if dp[s][i] == INF:
                continue
            for j in range(n):
                if s & (1<<j):
                    continue
                if dist[i][j] == INF:
                    continue
                ns = s | (1<<j)
                if dp[ns][j] > dp[s][i] + dist[i][j]:
                    dp[ns][j] = dp[s][i] + dist[i][j]
                    
    ans = INF
    full = (1<<n) - 1
    for i in range(n):
        if dp[full][i] != INF and dist[i][0] != INF:
            total = dp[full][i] + dist[i][0]
            if total < ans:
                ans = total
                
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.