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

javaimport java.util.*;class Solution {public long[] minTimeMaxPower(int n, int[][] edges, int power, int[] cost, int source, int target) {// 建图Listint[][] graph new List[n];for (int i 0; i n; i) {graph[i] new ArrayList();}for (int[] e : edges) {graph[e[0]].add(new int[]{e[1], e[2]});}// dist[node][rem] 到达 node 且剩余电量为 rem 的最短时间long[][] dist new long[n][power 1];for (int i 0; i n; i) {Arrays.fill(dist[i], Long.MAX_VALUE);}dist[source][power] 0;// 优先队列按时间升序时间相同时剩余电量大的优先存储 -rem 以便降序PriorityQueuelong[] pq new PriorityQueue((a, b) - {if (a[0] ! b[0]) return Long.compare(a[0], b[0]);return Long.compare(a[1], b[1]); // a[1] 是 -rem越小 rem 越大});pq.offer(new long[]{0, -power, source});while (!pq.isEmpty()) {long[] cur pq.poll();long time cur[0];int rem (int) -cur[1];int u (int) cur[2];// 跳过过期状态if (time ! dist[u][rem]) continue;// 到达目标此时必为最优最小时间且电量最大if (u target) {return new long[]{time, rem};}// 剩余电量不足以离开当前节点if (rem cost[u]) continue;int newRem rem - cost[u];for (int[] edge : graph[u]) {int v edge[0];int t edge[1];long newTime time t;if (newTime dist[v][newRem]) {dist[v][newRem] newTime;pq.offer(new long[]{newTime, -newRem, v});}}}// 不可达return new long[]{-1, -1};}}关键点说明· 分层图状态(节点, 剩余电量)用 dist[node][rem] 记录到达该状态的最小时间。· 优先级规则优先队列先按时间升序时间相同则剩余电量降序通过存储 -rem 实现。第一次弹出 target 时即获得全局最优解。· 电量消耗只在离开节点时消耗 cost[u]到达目标节点不消耗因为不继续移动。· 特殊情形若 source target直接返回 [0, power]。不可达则返回 [-1, -1]。