DeepSeek LeetCode 3977. 有限电量到达目标节点的最少时间 Python3实现

pythonimport heapqfrom typing import Listclass Solution:def minTimeMaxPower(self, n: int, edges: List[List[int]], power: int, cost: List[int], source: int, target: int) - List[int]:# 建图graph [[] for _ in range(n)]for u, v, t in edges:graph[u].append((v, t))# dist[node][rem] 到达该状态的最小时间初始为无穷大INF 10**18dist [[INF] * (power 1) for _ in range(n)]dist[source][power] 0# 优先队列(时间, -剩余电量, 节点)# 时间升序剩余电量降序通过 -rem 实现pq [(0, -power, source)]while pq:time, neg_rem, u heapq.heappop(pq)rem -neg_rem# 跳过过时的状态if time ! dist[u][rem]:continue# 到达目标此时一定是最小时间且剩余电量最大if u target:return [time, rem]# 如果剩余电量不足以离开当前节点则无法继续if rem cost[u]:continuenew_rem rem - cost[u]for v, t in graph[u]:new_time time tif new_time dist[v][new_rem]:dist[v][new_rem] new_timeheapq.heappush(pq, (new_time, -new_rem, v))# 不可达return [-1, -1]核心思路· 状态定义dist[node][rem] 表示到达节点 node 且剩余电量为 rem 时的最小时间。· Dijkstra 分层图将电量视为第二维每条边的转移会减少电量离开节点时消耗。· 优先级策略优先队列按 (时间, -剩余电量) 排序保证第一次弹出目标节点时时间最小且电量最大。· 剪枝若当前剩余电量无法支付 cost[u]则该状态无法继续扩展。复杂度· 时间O(E * power * log(n * power))其中 E 是边数。· 空间O(n * power)。特殊情况· source target 时直接返回 [0, power]无需消耗电量。· 若图不可达返回 [-1, -1]。