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

相关新闻

Jmeter安装插件-Response Times Over Time-查看并发结果

Jmeter安装插件-Response Times Over Time-查看并发结果

install插件网址:JMeter Plugins Manager :: JMeter-Plugins.org 安装后重启:

2026/8/23 7:36:48 阅读更多 →
机器学习在母婴健康风险评估中的应用:以孕妇吸烟与胎儿健康为例

机器学习在母婴健康风险评估中的应用:以孕妇吸烟与胎儿健康为例

1. 项目概述:当数据科学遇见母婴健康母婴健康一直是公共卫生和临床医学关注的核心领域,而孕妇吸烟对胎儿发育的潜在危害,更是被广泛讨论却难以精确量化的复杂问题。传统的流行病学研究依赖于问卷调查和回顾性分析,往往受限于样本量…

2026/8/23 7:36:48 阅读更多 →
大模型预训练数据要求 + 完整数据清洗流程

大模型预训练数据要求 + 完整数据清洗流程

一、预训练数据核心要求 1. 基础维度要求表 维度详细标准说明数据规模千亿~万亿 Token 级别通用大模型依赖海量文本,数据量不足会出现知识匮乏、逻辑差领域多样性通用:网页、书籍、论文、对话、代码、百科、新闻单一领域数据会造成模型偏科…

2026/8/23 7:36:48 阅读更多 →

最新新闻

嵌入式大赛命题解析:从瑞芯微RK3568到边缘AI实战

嵌入式大赛命题解析:从瑞芯微RK3568到边缘AI实战

1. 项目概述:一次产教融合的深度实践最近在嵌入式圈子里,一个消息引起了不小的讨论:飞凌嵌入式与瑞芯微正式成为2025年全国大学生嵌入式大赛的命题企业。这不仅仅是一个简单的商业合作新闻,对于像我这样长期关注嵌入式技术发展和人…

2026/8/23 8:26:31 阅读更多 →
深入解析JavaScript事件循环:从原理到高并发实战

深入解析JavaScript事件循环:从原理到高并发实战

这次我们来看一个前端、Node.js、Python 等现代编程中绕不开的核心概念:事件循环。它不是某个具体的开源项目,而是驱动异步编程的底层引擎。理解它,你就能明白为什么setTimeout不总是准时、Promise和async/await如何不阻塞主线程、以及高并发…

2026/8/23 8:26:31 阅读更多 →
构建可复现的机器学习Pipeline:从数据到部署的工程化实践

构建可复现的机器学习Pipeline:从数据到部署的工程化实践

在机器学习项目实践中,很多开发者都曾遇到过这样的困境:模型在离线测试集上表现优异,但一上线就效果骤降;或者项目初期进展迅速,到了特征工程和模型迭代阶段却陷入混乱,代码难以维护,实验无法复…

2026/8/23 8:26:31 阅读更多 →
经纬度到平面坐标转换:割草机路径规划中的坐标投影实战

经纬度到平面坐标转换:割草机路径规划中的坐标投影实战

1. 项目概述:当割草机遇上经纬度 最近在做一个挺有意思的项目,核心是把一个看似简单的物理问题——割草机的路径规划,和地理信息系统(GIS)里最基础的经纬度坐标转换给结合起来了。听起来是不是有点跨界?其实…

2026/8/23 8:26:31 阅读更多 →
ChatGPT Plus文件分析教程:PDF和Excel的读取与检查

ChatGPT Plus文件分析教程:PDF和Excel的读取与检查

文章目录 概要整体架构流程技术名词解释技术细节小结 概要 提示:这里可以添加技术概要 例如: openAI 的 GPT 大模型的发展历程。 整体架构流程 提示:这里可以添加技术整体架构 例如: 在语言模型中,编码器和解码器都…

2026/8/23 8:26:30 阅读更多 →
模型构建三大路径:代码驱动、可视化与混合式构建全解析

模型构建三大路径:代码驱动、可视化与混合式构建全解析

1. 项目概述:模型构建的三种核心路径 在数据驱动的决策和自动化流程中,模型构建是核心环节。无论是数据分析师想预测下季度的销售额,还是工程师需要自动化处理地理信息数据,都绕不开“如何构建一个模型”这个问题。我从业这些年&a…

2026/8/23 8:25:28 阅读更多 →

日新闻

[光学原理与应用-521]:对光的错误理解与纠偏

[光学原理与应用-521]:对光的错误理解与纠偏

首先光是一种能量的载体和形态,宏观上观察到的光是由无数个微观的光量子组成的,每个光子在产生的瞬间,其在真空的空间中以确定不变的速度沿着一个初始的方向一直向前,在微观层面,每个光量子的运动轨迹是以波函数所展现…

2026/8/23 0:00:50 阅读更多 →
SIP通话转接原理与REFER方法实战解析

SIP通话转接原理与REFER方法实战解析

1. 通话转接不是“挂断再拨号”,而是SIP会话的动态重定向你有没有遇到过这样的场景:客服坐席A正在和客户通电话,突然需要把这通对话无缝转给专家坐席B,客户完全感知不到中间的断连——既没听到忙音,也没被要求重新拨号…

2026/8/23 0:00:50 阅读更多 →
Kolla-ansible单节点OpenStack部署实战:从环境准备到排坑指南

Kolla-ansible单节点OpenStack部署实战:从环境准备到排坑指南

1. 为什么选择Kolla-ansible来部署单节点OpenStack?如果你正在寻找一种能把OpenStack从“概念”快速变成“可用的实验环境”的方法,那么Kolla-ansible几乎是当前最主流、最省心的选择。我见过太多人卡在手动编译依赖、配置服务、处理版本冲突的泥潭里&am…

2026/8/23 0:00:50 阅读更多 →

周新闻

[光学原理与应用-521]:对光的错误理解与纠偏

[光学原理与应用-521]:对光的错误理解与纠偏

首先光是一种能量的载体和形态,宏观上观察到的光是由无数个微观的光量子组成的,每个光子在产生的瞬间,其在真空的空间中以确定不变的速度沿着一个初始的方向一直向前,在微观层面,每个光量子的运动轨迹是以波函数所展现…

2026/8/23 0:00:50 阅读更多 →
SIP通话转接原理与REFER方法实战解析

SIP通话转接原理与REFER方法实战解析

1. 通话转接不是“挂断再拨号”,而是SIP会话的动态重定向你有没有遇到过这样的场景:客服坐席A正在和客户通电话,突然需要把这通对话无缝转给专家坐席B,客户完全感知不到中间的断连——既没听到忙音,也没被要求重新拨号…

2026/8/23 0:00:50 阅读更多 →
Kolla-ansible单节点OpenStack部署实战:从环境准备到排坑指南

Kolla-ansible单节点OpenStack部署实战:从环境准备到排坑指南

1. 为什么选择Kolla-ansible来部署单节点OpenStack?如果你正在寻找一种能把OpenStack从“概念”快速变成“可用的实验环境”的方法,那么Kolla-ansible几乎是当前最主流、最省心的选择。我见过太多人卡在手动编译依赖、配置服务、处理版本冲突的泥潭里&am…

2026/8/23 0:00:50 阅读更多 →

月新闻

免费解锁百度网盘SVIP加速:macOS用户必备的下载提速终极指南

免费解锁百度网盘SVIP加速:macOS用户必备的下载提速终极指南

免费解锁百度网盘SVIP加速:macOS用户必备的下载提速终极指南 【免费下载链接】BaiduNetdiskPlugin-macOS For macOS.百度网盘 破解SVIP、下载速度限制~ 项目地址: https://gitcode.com/gh_mirrors/ba/BaiduNetdiskPlugin-macOS 还在为百度网盘macOS版的龟速下…

2026/8/22 18:08:39 阅读更多 →
终极ncmdump指南:3分钟实现网易云NCM音乐解密与格式转换

终极ncmdump指南:3分钟实现网易云NCM音乐解密与格式转换

终极ncmdump指南:3分钟实现网易云NCM音乐解密与格式转换 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump 还在为网易云音乐下载的NCM格式文件无法在其他播放器播放而烦恼吗?ncmdump解密工具帮你轻松解决这个困…

2026/8/22 7:31:03 阅读更多 →
HarmonyOS 应用开发《掌上英语》第81篇: 智能体卡片:为英语学习 App 打造桌面级学习助手

HarmonyOS 应用开发《掌上英语》第81篇: 智能体卡片:为英语学习 App 打造桌面级学习助手

AgentCard 智能体卡片:为英语学习 App 打造桌面级学习助手适用平台:HarmonyOS 7.0 (API 26 Beta)一、引言 HarmonyOS 7.0(API 26 Beta)新增了 AgentCard 智能体卡片能力,这是继 HMAF(鸿蒙智能体框架&#x…

2026/8/22 3:22:48 阅读更多 →