Kimi LeetCode LCP 35. 电动车游城市 Java实现

根据已收集的信息我来为你提供 LCP 35. 电动车游城市 的 Java 实现。题目分析这道题是分层图最短路问题。核心思路是将状态定义为 (城市, 电量) 二元组然后使用 Dijkstra 算法求最短时间。- 状态设计dist[i][j] 表示到达第 i 个城市时剩余 j 单位电量的最小耗时- 两种转移1. 充电在当前城市充 1 单位电花费 charge[i] 时间电量 1不超过 cnt2. 行驶前往相邻城市花费路程距离的时间电量 -路程需保证电量足够Java 实现Dijkstra 分层图javaimport java.util.*;class Solution {// 状态类记录当前时间、所在城市、剩余电量static class State implements ComparableState {int time; // 当前总耗时int city; // 当前城市int power; // 剩余电量State(int time, int city, int power) {this.time time;this.city city;this.power power;}// 按总耗时升序用于优先队列Overridepublic int compareTo(State other) {return this.time - other.time;}}public int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {int n charge.length;// 建图邻接表存储无向图Listint[][] graph new ArrayList[n];for (int i 0; i n; i) {graph[i] new ArrayList();}for (int[] path : paths) {int u path[0], v path[1], w path[2];graph[u].add(new int[]{v, w});graph[v].add(new int[]{u, w});}// dist[i][j] 到达城市i剩余j电量的最小耗时int[][] dist new int[n][cnt 1];for (int i 0; i n; i) {Arrays.fill(dist[i], Integer.MAX_VALUE);}dist[start][0] 0;// Dijkstra优先队列按总耗时排序PriorityQueueState pq new PriorityQueue();pq.offer(new State(0, start, 0));while (!pq.isEmpty()) {State cur pq.poll();int time cur.time, city cur.city, power cur.power;// 如果当前状态不是最优跳过if (time dist[city][power]) continue;// 到达终点直接返回Dijkstra保证第一次到终点即最优if (city end) {return time;}// 操作1在当前城市充1单位电如果未满if (power cnt) {int newTime time charge[city];int newPower power 1;if (newTime dist[city][newPower]) {dist[city][newPower] newTime;pq.offer(new State(newTime, city, newPower));}}// 操作2前往相邻城市电量足够时for (int[] edge : graph[city]) {int nextCity edge[0];int cost edge[1]; // 路程 耗电 时间if (power cost) { // 电量足够int newTime time cost;int newPower power - cost;if (newTime dist[nextCity][newPower]) {dist[nextCity][newPower] newTime;pq.offer(new State(newTime, nextCity, newPower));}}}}// 题目保证可达这里为了代码完整性return -1;}}关键点解释要点 说明分层图思想 将一维的城市扩展为二维的(城市, 电量)状态充电转移 在同一城市层内电量 j → j1时间 charge[i]行驶转移 跨城市层电量 j → j-w时间 ww为路程优先队列 保证每次扩展的都是当前耗时最少的状态确保第一次到终点即为最优解复杂度分析- 时间复杂度O((N \cdot C) \cdot \log(N \cdot C) M \cdot C)其中 N 为城市数C 为最大电量 cntM 为边数- 空间复杂度O(N \cdot 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]- 最优路径1 - 3 - 0- 城市1充3单位电耗时 3*10 30行驶到3耗电3- 城市3充5单位电耗时 5*1 5行驶到0耗电5- 总耗时30 5 3 5 43 ✓这个实现是标准的分层图最短路 Dijkstra 解法效率较高且思路清晰。