以下是 LeetCode 3594. 所有人渡河所需的最短时间 的 Python3 实现。解题思路这道题的关键在于状态可能循环转移人可以来回过河阶段也是周期性的因此不能用普通的状压 DP而应该用 Dijkstra 最短路。状态定义- mask未过河人员的位掩码n ≤ 12共 2^n 个状态- dir船的方向0在起点/未过河侧1在终点/已过河侧- stage当前环境阶段0 m-1状态转移- 船在起点时从剩余人员中选出 1k 人过河- 船在终点时从已过河人员中选 1 人把船开回来- 渡河时间 组内最大 time[i] × mul[stage]阶段前进 floor(时间) % m 步Python3 代码pythonimport heapqimport mathfrom typing import Listclass Solution:def minTime(self, n: int, k: int, m: int, time: List[int], mul: List[float]) - float:FULL (1 n) - 1# 预处理每个子集的最大 time[i]mask_time [0] * (1 n)for mask in range(1 n):for i in range(n):if mask (1 i):mask_time[mask] max(mask_time[mask], time[i])# 预处理每个 mask 下可选的合法子集人数不超过 k# g[ppl] 表示从剩余人员 ppl 中可以选出的所有合法过河组合g [[] for _ in range(1 n)]for ppl in range(1 n):sub pplwhile sub 0:if sub.bit_count() k:g[ppl].append(sub)sub (sub - 1) ppl# dist[mask][dir][stage] 最短时间INF float(inf)dist [[[INF] * m for _ in range(2)] for _ in range(1 n)]h []def push(cost, mask, dir, stage):if cost dist[mask][dir][stage]:dist[mask][dir][stage] costheapq.heappush(h, (cost, mask, dir, stage))# 初始状态所有人未过河船在起点阶段0push(0.0, FULL, 0, 0)while h:cost, mask, dir, stage heapq.heappop(h)if cost dist[mask][dir][stage]:continueif dir 0: # 船在起点送人过河for sub in g[mask]:d mask_time[sub] * mul[stage]new_cost cost dnew_mask mask ^ sub # 这些人过河了new_stage (stage math.floor(d)) % mpush(new_cost, new_mask, 1, new_stage)else: # 船在终点需要1人返回if mask 0: # 所有人都过河了return cost# 已过河的人 FULL ^ maskarrived FULL ^ masksub arrivedwhile sub 0:# 选其中1人返回sub 只有1个bit时才是单人if sub.bit_count() 1:d mask_time[sub] * mul[stage]new_cost cost dnew_mask mask | sub # 这个人回到起点侧new_stage (stage math.floor(d)) % mpush(new_cost, new_mask, 0, new_stage)sub (sub - 1) arrivedreturn -1.0代码说明部分 作用mask_time 预处理 O(2^n × n) 计算每个子集的最大时间g 预处理 对每个剩余人员集合预存所有合法的过河子集≤k人加速枚举Dijkstra 状态为 (mask, dir, stage)按总时间优先扩展dir0 在起点枚举子集送人过河dir1 在终点枚举已过河的人中派1人返回复杂度- 时间复杂度状态数 × 转移数 ≈ O(2^n × 2 × m × C(n,k))n ≤ 12, k ≤ 5, m ≤ 5完全可接受- 空间复杂度O(2^n × 2 × m) 用于 dist 数组注意点1. 返回的人不限于刚过河的人——可以是之前留在对岸的任何人2. 阶段周期性变化——new_stage (stage floor(d)) % m3. 可以故意来回过河——利用 Dijkstra 自动处理可能为了等到更优的 mul 阶段4. 无法渡河的情况——如 n2, k1 时送1人过去后没人能回来接返回 -1