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 解法效率较高且思路清晰。

相关新闻

最新新闻

数据结构与算法核心精讲:从概念到代码实战

数据结构与算法核心精讲:从概念到代码实战

这次我们来看一个所有程序员都绕不开的基础话题:数据结构与算法。无论你是刚入门的新手,还是准备面试的求职者,或是想夯实基础的开发者,理解这些核心概念都是写出高效、健壮代码的第一步。这篇文章不讲复杂的数学推导,…

2026/8/23 8:16:09
SpringBoot智慧校园招聘系统设计与实践

SpringBoot智慧校园招聘系统设计与实践

1. 项目背景与核心价值 高校就业招聘一直是连接学生与企业的重要桥梁。传统线下招聘会存在信息不对称、效率低下、匹配度不高等痛点。我在实际参与校园招聘工作时发现,学生往往需要奔波于各个宣讲会现场,而企业HR也苦于无法精准触达目标人才。基于Spring…

2026/8/23 8:16:09
从“不高兴的津津”详解模拟题解题框架:需求拆解、代码实现与测试验证

从“不高兴的津津”详解模拟题解题框架:需求拆解、代码实现与测试验证

1. 从“不高兴的津津”说起:一道经典题目的再思考最近在整理蓝桥杯的练习题时,又看到了这道“不高兴的津津”。题目本身很简单,几乎是所有编程初学者在接触循环和条件判断后都会遇到的经典例题。它的核心是计算一周内哪天的不高兴程度最高&am…

2026/8/23 8:16:09
Java全栈面试宝典:高频考点与实战解析

Java全栈面试宝典:高频考点与实战解析

1. 为什么需要Java全栈面试宝典?最近三年Java全栈岗位的竞争激烈程度增长了近300%。根据国内主流招聘平台数据显示,一个中级Java全栈工程师岗位平均会收到150份简历。在这样的环境下,系统化的面试准备已经成为求职者的刚需。我整理这份宝典的…

2026/8/23 8:16:09
考研数学导数定义题:从函数极限到桥梁思维的解题突破

考研数学导数定义题:从函数极限到桥梁思维的解题突破

考研数学中,导数定义题是每年必考且区分度极高的题型。很多同学复习时,把导数定义简单理解为“极限公式”,刷了大量常规题,但一遇到结合函数极限的“开放性”题目,或者题干信息不全、需要自己构造的“妙用”题&#xf…

2026/8/23 8:16:09
Spring Boot + 小程序智能旅行助手90473----景点推荐 · AI 问答 · 旅游论坛 · 后台运营管理

Spring Boot + 小程序智能旅行助手90473----景点推荐 · AI 问答 · 旅游论坛 · 后台运营管理

摘要围绕旅游信息查询、个性化推荐和互动交流,系统采用 Java 与 Spring Boot 构建后端,小程序作为用户端,MySQL 负责数据存储。旅行用户可以筛选景点、查看推荐、评分互动、使用 AI 助手并参与旅游论坛;管理员通过后台维护景点、用…

2026/8/23 8:11:09