企业官网建设流程全解析

以下是 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 代码

```python
import heapq
import math
from typing import List

class 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 = ppl
while 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] = cost
heapq.heappush(h, (cost, mask, dir, stage))

# 初始状态：所有人未过河，船在起点，阶段0
push(0.0, FULL, 0, 0)

while h:
cost, mask, dir, stage = heapq.heappop(h)

if cost > dist[mask][dir][stage]:
continue

if dir == 0: # 船在起点，送人过河
for sub in g[mask]:
d = mask_time[sub] * mul[stage]
new_cost = cost + d
new_mask = mask ^ sub # 这些人过河了
new_stage = (stage + math.floor(d)) % m
push(new_cost, new_mask, 1, new_stage)
else: # 船在终点，需要1人返回
if mask == 0: # 所有人都过河了
return cost
# 已过河的人 = FULL ^ mask
arrived = FULL ^ mask
sub = arrived
while sub > 0:
# 选其中1人返回（sub 只有1个bit时才是单人）
if sub.bit_count() == 1:
d = mask_time[sub] * mul[stage]
new_cost = cost + d
new_mask = mask | sub # 这个人回到起点侧
new_stage = (stage + math.floor(d)) % m
push(new_cost, new_mask, 0, new_stage)
sub = (sub - 1) & arrived

return -1.0
```

代码说明

部分 作用
`mask_time` 预处理 O(2^n × n) 计算每个子集的最大时间
`g` 预处理 对每个剩余人员集合，预存所有合法的过河子集（≤k人），加速枚举
Dijkstra 状态为 `(mask, dir, stage)`，按总时间优先扩展
`dir=0` 在起点，枚举子集送人过河
`dir=1` 在终点，枚举已过河的人中派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)) % m`
3. 可以故意来回过河——利用 Dijkstra 自动处理，可能为了等到更优的 `mul` 阶段
4. 无法渡河的情况——如 n=2, k=1 时，送1人过去后没人能回来接，返回 `-1`