算法笔试模拟题精解之“最短路”

简介: 做这道题的思路是,假设一开始没有道路,只有n个水库。建立一个连通图,初始状态连通图中只有水库1一个结点。然后将逐步将道路加入连通图中,道路加入连通图的条件是道路两端的水库至少有一个在连通图中,道路加入连通图后,道路两端的水库都加入连通图。

在线编程介绍

阿里云开发者社区在线编程产品,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,为用户营造专心答题的学习环境。
本文为大家介绍其中的 第95题:最短路 的题目解析

题目描述

题目等级:容易
知识点:最短路、DP

《缺氧》是Klei Entertainment所制作并发行的一款模拟游戏。这是一个太空殖民地模拟游戏,玩家需要管理你的复制人,帮助他们挖掘、建立和维护一个地下的小行星基地。你需要水、食物、氧气、适当的调节压力和适宜的温度来维持他们活着并满足他们。
在这里,氧气是必不可少的,没有氧气,复制人就会无法生存。电解制氧是一个非常实用的制氧方法,将水通过电解器之后,电解器会消耗水产生氧气和氢气,氧气可以供小人呼吸,氢气则可以进行氢气发电。
复制人在进行了一段时间的挖掘之后,在地图里发现了n个水库,他们的命名方法非常暴力,水库1,水库2,...,水库n。他们挖掘了m条道路将这n个水库联通,现在复制人想知道水库1到水库n的最短距离。

输入水库数n、挖掘的道路条数m (1<= n,m <= 1000)和一个二维数组a,其中a[i]=[x,y,z] (1 <= x,y,z <= 1000) 表示水库x与水库y之间的道路长度为z。

输出水库1到水库n之间的最短距离。

示例1
输入:
5
7
[[1,2 ,3],[1 ,2 ,1],[1 ,5 ,10],[2 ,3 ,4],[2, 4, 10],[2, 5 ,8],[3 ,3 ,9]]
输出:
9

解题思路:DP

本题需要用到动态规划算法。

首先可以创建一个数组记录水库1到其他各个水库的最短距离。做这道题的思路是,假设一开始没有道路,只有n个水库。建立一个连通图,初始状态连通图中只有水库1一个结点。然后将逐步将道路加入连通图中,道路加入连通图的条件是道路两端的水库至少有一个在连通图中,道路加入连通图后,道路两端的水库都加入连通图。

每当有一条道路加入连通图时,计算水库1到此道路两端的水库的最短距离是否可以因为这条道路的加入而更短。如果可以,更新水库1到这些水库的距离。

当所有道路加入连通图后,数组中记录的水库1到水库n的距离即为所求最短距离。

时间复杂度:O(n)
空间复杂度:O(n)

看完之后是不是有了想法了呢,快来练练手吧>>

720-150.png

相关文章
|
存储 算法 安全
国密算法及简单使用
国密算法,即国家密码局认定的国产密码算法,主要用于保护国家关键信息基础设施和商业领域的加密通信和数据安全。根据 2019年10月26日第十三届全国人民代表大会常务委员会第十四次会议通过的《中华人民共和国密码法》,国家对密码实行分类管理,密码分为核心密码、普通密码和商用密码
2910 4
|
存储 人工智能 Serverless
AI Agent 运行时相比传统应用有什么不同:百家企业 AI 实践观察(二)
本文深入探讨了AI Agent运行时的核心挑战及解决方案,分析了AI Agent从理论走向实践过程中所面临的动态推理、资源成本与安全风险等问题,并详细介绍了阿里云函数计算FC如何作为AI Agent运行时及沙箱环境(Sandbox),有效应对脉冲式计算需求、突发性负载、数据隔离与会话亲和性等挑战。同时,文章结合典型场景,展示了函数计算FC在编码式与流程式AI Agent构建中的优势,涵盖Chat AI Agent、营销素材组装、仿真训练等应用,为AI Agent的高效、安全运行提供了完整的技术路径。
1316 2
|
3天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
1661 2
|
6天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
6天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
3天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
3177 0
|
19天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
8547 58
|
13天前
|
Linux 开发工具 iOS开发
2026最新codex下载安装保姆级使用教程(下载+安装+登录+使用,含所有历史版本)
本文详解OpenAI Codex国内快速上手指南:提供Win/macOS/Linux全平台免安装包、npm/Homebrew等多方式安装、账号/API Key双登录、简体中文切换,覆盖下载、安装、汉化、使用及高频避坑(如微软商店失败、npm超时等),10分钟即可跑通。
3034 9
|
19天前
|
JavaScript API iOS开发
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(DSH)是DeepSeek于2026年开源的MIT协议AI Agent框架,支持插件化组装模型、工具、沙箱与UI,兼容主流大模型。本文提供免Node.js的桌面端安装包(Win/macOS),含详细图文教程及热门插件推荐。
5814 69