以下是 LCP 35. 电动车游城市 的 Python3 实现采用 分层图最短路 Dijkstra 算法。---解题思路这是一道经典的分层图最短路问题。核心思想是将状态定义为 (城市, 电量) 二元组然后在这个扩展的状态空间上运行 Dijkstra 算法 。状态空间- 节点(城市 i, 电量 c)其中 0 c cnt- 充电边(i, c) → (i, c1)权重 charge[i]充 1 单位电的时间- 行驶边(i, c) → (j, c-w)权重 w行驶距离 时间要求 c w为什么第一次到达终点就是最优解因为 Dijkstra 按总时间从小到大扩展第一次从优先队列中取出终点状态时即为全局最短时间。---Python3 代码pythonimport heapqfrom typing import Listclass 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在当前城市充电电量1if power cnt:new_cost cost charge[city]if new_cost dist[city][power 1]:dist[city][power 1] new_costheapq.heappush(pq, (new_cost, city, power 1))# 操作2前往相邻城市电量减少时间增加for nxt, w in graph[city]:if power w: # 电量足够到达下一个城市new_power power - wnew_cost cost wif new_cost dist[nxt][new_power]:dist[nxt][new_power] new_costheapq.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]], cnt6, start1, end0, charge[2,10,4,1] 43 路线 1→3→0充电 3×10 5×1 35行驶 3 5 82 paths[[0,4,2],[4,3,5],[3,0,5],[0,1,5],[3,2,4],[1,2,8]], cnt8, start0, end2, 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)
