企业官网建设流程全解析

以下是 LCP 35. 电动车游城市 的 Python3 实现，采用 分层图最短路 + Dijkstra 算法。

---

解题思路

这是一道经典的分层图最短路问题。核心思想是将状态定义为 (城市, 电量) 二元组，然后在这个扩展的状态空间上运行 Dijkstra 算法 。

状态空间：
- 节点：`(城市 i, 电量 c)`，其中 `0 <= c <= cnt`
- 充电边：`(i, c) → (i, c+1)`，权重 = `charge[i]`（充 1 单位电的时间）
- 行驶边：`(i, c) → (j, c-w)`，权重 = `w`（行驶距离 = 时间，要求 `c >= w`）

为什么第一次到达终点就是最优解？
因为 Dijkstra 按总时间从小到大扩展，第一次从优先队列中取出终点状态时，即为全局最短时间。

---

Python3 代码

```python
import heapq
from typing import List

class Solution:
"""
LCP 35. 电动车游城市

小明的电动车电量充满时可行驶距离为 cnt，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间。
地图上共有 N 个景点，景点编号为 0 ~ N-1。
paths 表示城市间的双向通路及距离。
初始状态，电动车电量为 0。每个城市都设有充电桩，charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。
返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end。

算法：分层图最短路 + Dijkstra
状态：(城市, 电量) 二元组
"""

def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:
n = len(charge)

# 建图：邻接表
graph = [[] for _ in range(n)]
for u, v, w in paths:
graph[u].append((v, w))
graph[v].append((u, w))

# dist[i][c] = 到达城市 i 且剩余电量为 c 时的最小时间
INF = float('inf')
dist = [[INF] * (cnt + 1) for _ in range(n)]
dist[start][0] = 0

# Dijkstra 优先队列：(总时间, 城市, 电量)
pq = [(0, start, 0)]

while pq:
cost, city, power = heapq.heappop(pq)

# 如果已经找到更优解，跳过
if cost > dist[city][power]:
continue

# 到达终点，直接返回（Dijkstra 保证第一次到达终点就是最优解）
if city == end:
return cost

# 操作1：在当前城市充电（电量+1）
if power < cnt:
new_cost = cost + charge[city]
if new_cost < dist[city][power + 1]:
dist[city][power + 1] = new_cost
heapq.heappush(pq, (new_cost, city, power + 1))

# 操作2：前往相邻城市（电量减少，时间增加）
for nxt, w in graph[city]:
if power >= w: # 电量足够到达下一个城市
new_power = power - w
new_cost = cost + w
if new_cost < dist[nxt][new_power]:
dist[nxt][new_power] = new_cost
heapq.heappush(pq, (new_cost, nxt, new_power))

# 题目保证所有城市相互可以到达，所以不会执行到这里
return -1
```

---

复杂度分析

- 时间复杂度：O((N \times C + M \times C) \log(N \times C))，其中 N 为城市数，C = cnt 为最大电量，M 为路径数。每个状态最多被扩展一次，每次扩展涉及充电和行驶两种操作。
- 空间复杂度：O(N \times C + M)，用于存储距离数组、优先队列和邻接表。

---

示例验证

示例 输入 输出 解释
1 `paths=[[1,3,3],[3,2,1],[2,1,3],[0,1,4],[3,0,5]]`, `cnt=6`, `start=1`, `end=0`, `charge=[2,10,4,1]` `43` 路线 `1→3→0`，充电 `3×10 + 5×1 = 35`，行驶 `3 + 5 = 8`
2 `paths=[[0,4,2],[4,3,5],[3,0,5],[0,1,5],[3,2,4],[1,2,8]]`, `cnt=8`, `start=0`, `end=2`, `charge=[4,1,1,3,2]` `38` 路线 `0→4→3→2`，充电 `4×2 + 2×8 + 3×1 = 27`，行驶 `2 + 5 + 4 = 11`

---

下载文件：[lcp35_electric_car_plan.py](sandbox:///mnt/agents/output/lcp35_electric_car_plan.py)