Overview

This problem is a variant of the Traveling Salesman Problem (TSP), where we need to find the shortest route that starts from a specified starting point, visits all delivery destinations in any order, and returns to the starting point.

Analysis

• If we exhaustively search all routes visiting every delivery destination, we would need to try \(K!\) permutations. Since \(K \leq 15\), this results in up to \(15! \approx 1.3 \times 10^{12}\) possibilities, which is too large for a brute-force approach to finish in time.
• Additionally, since it is allowed to pass through the same point or road multiple times, we need to precompute all-pairs shortest paths when finding the shortest route.
• A key observation is that only the starting point \(S\) and the \(K\) delivery destinations actually matter. Other points only serve as intermediate waypoints, so after computing all-pairs shortest paths, we can extract just these important points and solve the TSP on them.

Algorithm

1. Floyd–Warshall Algorithm: First, compute all-pairs shortest paths. This gives us the shortest distance between any two points in \(O(N^3)\).
2. Extracting Important Points: Extract the set of \(n = K+1\) points consisting of the starting point \(S\) and the \(K\) delivery destinations.
3. Traveling Salesman Problem (TSP): Solve the TSP on the extracted \(n\) points. Using dynamic programming, represent the state as a “bitmask of visited points” and “current point”, computing in \(O(2^n \cdot n^2)\).
4. Computing the Final Route: After visiting all points, add the cost of returning to the starting point \(S\) and find the minimum value.

Complexity

• Time complexity: \(O(N^3 + 2^n \cdot n^2)\) (where \(n = K+1\))
• Space complexity: \(O(N^2 + 2^n \cdot n)\)

Implementation Notes

• Before running the Floyd–Warshall algorithm, initialize the cost of self-loops (moving from \(i\) to \(i\)) to \(0\).

• To ensure no duplicates in the set of important points, use a set to extract unique points.

• In the initial state of the dynamic programming, only the starting point \(S\) is marked as visited (set the corresponding bit in the bitmask), with a cost of \(0\).

• Finally, from the state where all points have been visited, add the cost of returning to the starting point and find the minimum value.

  Source Code

def main():
    import sys
    from itertools import permutations

    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return

    idx = 0
    N = int(data[idx]); M = int(data[idx+1]); idx += 2
    INF = 10**18
    dist = [[INF] * (N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        dist[i][i] = 0

    for _ in range(M):
        u = int(data[idx]); v = int(data[idx+1]); w = int(data[idx+2]); idx += 3
        if w < dist[u][v]:
            dist[u][v] = w

    S = int(data[idx]); K = int(data[idx+1]); idx += 2
    T_list = [int(data[idx+i]) for i in range(K)]
    targets = [S] + T_list
    unique_nodes = sorted(set(targets))
    mapping = {}
    for i, node in enumerate(unique_nodes):
        mapping[node] = i
    n_nodes = len(unique_nodes)
    new_dist = [[INF] * n_nodes for _ in range(n_nodes)]

    for k in range(1, N+1):
        for i in range(1, N+1):
            if dist[i][k] == INF:
                continue
            for j in range(1, N+1):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    for i, u in enumerate(unique_nodes):
        for j, v in enumerate(unique_nodes):
            new_dist[i][j] = dist[u][v]

    dp = [[INF] * n_nodes for _ in range(1<<n_nodes)]
    start_index = mapping[S]
    dp[1<<start_index][start_index] = 0

    for mask in range(1<<n_nodes):
        for i in range(n_nodes):
            if dp[mask][i] == INF:
                continue
            for j in range(n_nodes):
                if mask & (1<<j):
                    continue
                new_mask = mask | (1<<j)
                cost = dp[mask][i] + new_dist[i][j]
                if cost < dp[new_mask][j]:
                    dp[new_mask][j] = cost

    full_mask = (1<<n_nodes) - 1
    ans = INF
    for i in range(n_nodes):
        if dp[full_mask][i] != INF:
            total = dp[full_mask][i] + new_dist[i][start_index]
            if total < ans:
                ans = total

    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.