🔗 AWC0022E Delivery Driver’s Route

Problem Statement

題目簡述

有 NN 個城鎮與 MM 條雙向道路。
從城鎮 11 出發，訪問所有城鎮至少各一次後回到城鎮 11。
求最短總路程；若不可能則輸出 −1-1。

Constraints

約束條件

  • 2≤N≤152 \leq N \leq 15
  • 1≤M≤N(N−1)21 \leq M \leq \frac{N(N-1)}{2}
  • 1≤Wi≤1061 \leq W_i \leq 10^6
  • 無自環、無重邊

思路：Floyd-Warshall + 狀壓 DP（TSP）

觀察：本質就是 TSP

由於可以重複經過同一條道路，而在任意兩點間移動時走最短路一定最優，因此可以先預處理所有點對的最短距離，再將問題轉化為：

問題轉化

在以最短距離為邊權的完全圖上，求從節點 00 出發、恰好訪問每個節點一次並回到起點的最短迴路——即經典的 旅行推銷員問題（TSP）。

第一步：Floyd-Warshall 全源最短路

用 Floyd-Warshall 在 O(N3)O(N^3) 內求出所有點對之間的最短距離 dist[u][v]。

若存在某個節點 uu 使得 dist[0][u] = ∞，表示從起點不可達，直接輸出 −1-1。

第二步：狀壓 DP 求解 TSP

為什麼想到狀壓 DP？

N≤15N \leq 15，這是狀壓 DP 的經典信號。用一個 NN 位元的 bitmask 表示「哪些城鎮已被訪問」，狀態數為 O(2N⋅N)O(2^N \cdot N)。

定義 dfs(u, s)：目前位於城鎮 uu，已訪問的城鎮集合為 ss（bitmask），要完成剩餘所有城鎮的訪問後回到起點的最小代價。

轉移：

dfs(u,s)=min⁡v∉s(dist[u][v]+dfs(v, s∪{v}))\text{dfs}(u, s) = \min_{v \notin s} \Big( \text{dist}[u][v] + \text{dfs}(v,\, s \cup \{v\}) \Big)

邊界：當 ss 包含所有節點時（s=2N−1s = 2^N - 1），回到起點的代價為 dist[u][0]。

初始呼叫：dfs(0, 1)，表示從節點 00 出發，初始已訪問集合為 {0}\{0\}。

複雜度分析

  • 時間複雜度：O(N3+2N⋅N2)\mathcal{O}(N^3 + 2^N \cdot N^2)。
    • Floyd-Warshall 為 N3N^3；
    • 狀壓 DP 有 2N⋅N2^N \cdot N 個狀態，每個轉移枚舉 NN 個下一步，因此為 2N⋅N22^N \cdot N^2
  • 空間複雜度：O(N2+2N⋅N)\mathcal{O}(N^2 + 2^N \cdot N)，分別為距離矩陣和 DP 記憶化表

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from functools import cache


def solve():
    N, M = map(int, input().split())
    dist = [[float("inf")] * N for _ in range(N)]
    for u in range(N):
        dist[u][u] = 0

    for _ in range(M):
        u, v, w = map(int, input().split())
        u, v = u - 1, v - 1
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w

    # Floyd-Warshall
    for k in range(N):
        for u in range(N):
            if dist[u][k] == float("inf"):
                continue
            for v in range(N):
                dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v])

    if any(dist[0][u] == float("inf") for u in range(N)):
        print(-1)
        return

    U = (1 << N) - 1

    @cache
    def dfs(u, s):
        if s == U:
            return dist[u][0]

        res = float("inf")
        for v in range(N):
            if s & (1 << v):
                continue
            res = min(res, dist[u][v] + dfs(v, s | (1 << v)))
        return res

    print(dfs(0, 1))


if __name__ == "__main__":
    solve()