LeetCode 1976.到达目的地的方案数:单源最短路的Dijkstra算法
【LetMeFly】1976.到达目的地的方案数:单源最短路的Dijkstra算法
力扣题目链接:https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/
你在一个城市里,城市由 n 个路口组成,路口编号为 0 到 n - 1 ,某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口,且任意两个路口之间最多有一条路。
给你一个整数 n 和二维整数数组 roads ,其中 roads[i] = [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。
请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大,将结果对 109 + 7 取余 后返回。
示例 1:
输入:n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]] 输出:4 解释:从路口 0 出发到路口 6 花费的最少时间是 7 分钟。 四条花费 7 分钟的路径分别为: - 0 ➝ 6 - 0 ➝ 4 ➝ 6 - 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6 - 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
示例 2:
输入:n = 2, roads = [[1,0,10]] 输出:1 解释:只有一条从路口 0 到路口 1 的路,花费 10 分钟。
提示:
1 <= n <= 200n - 1 <= roads.length <= n * (n - 1) / 2roads[i].length == 30 <= ui, vi <= n - 11 <= timei <= 109ui != vi- 任意两个路口之间至多有一条路。
- 从任意路口出发,你能够到达其他任意路口。
方法一:单源最短路的Dijkstra算法
“单源最短路”意思是从一个点出发到其他点的最短路径。单源最短路的Dijkstra算法也可以看我之前做的视频。
总之Dijkstra算法就是,我们从起点开始:
计算所有能一步到达的点中,哪个点距离起点最近。
下一步就走到这个点,然后能一步到达的点就更新了。
直到走完所有的点为止。
对于这道题,我们在“往前走”的同时,记录一下走到这一步的“方案数”:
- 若从当前点走到点
a的距离 小于a原本到起点的距离,则说明发现了新大“路”(更近的路)。舍弃掉之前的方案数,将点a的方案数变为当前点的方案数,并更新最短距离,可以从点a开始往深处继续探索。 - 若从当前点走到点
a的距离 等于a原本到起点的距离,则说明又发现了一条同为最近路的路。将点a的方案数加上当前点的方案数。 - 否则,已有更短路,不做考虑。
最终返回终点的路径数即为答案。
- 时间复杂度 O ( m log m ) O(m\log m) O(mlogm)
- 空间复杂度 O ( n + m ) O(n+m) O(n+m)
AC代码
C++
typedef long long ll;
const ll MOD = 1e9 + 7;class Solution {
public:int countPaths(int n, vector<vector<int>>& roads) {vector<vector<pair<int, int>>> graph(n);for (vector<int>& road : roads) {graph[road[0]].push_back({road[1], road[2]});graph[road[1]].push_back({road[0], road[2]});}vector<ll> way(n);way[0] = 1;vector<ll> dis(n, 1e18);dis[0] = 0;priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;pq.push({0, 0});while (pq.size()) {auto [thisDistance, thisNode] = pq.top();pq.pop();if (thisDistance > dis[thisNode]) { // 有更优解了continue;}for (auto [nextNode, nextDistance] : graph[thisNode]) {if (thisDistance + nextDistance < dis[nextNode]) {dis[nextNode] = thisDistance + nextDistance;way[nextNode] = way[thisNode];pq.push({dis[nextNode], nextNode});}else if (thisDistance + nextDistance == dis[nextNode]) {way[nextNode] = (way[nextNode] + way[thisNode]) % MOD;}}}return way.back();}
};
Python
# from typing import List
# import heapqMOD = int(1e9) + 7class Solution:def countPaths(self, n: int, roads: List[List[int]]) -> int:graph = [[] for _ in range(n)]for x, y, d in roads:graph[x].append((y, d))graph[y].append((x, d))way = [0] * nway[0] = 1dis = [int(1e18)] * ndis[0] = 0pq = [(0, 0)]while pq:thisDistance, thisNode = heapq.heappop(pq)if thisDistance > dis[thisNode]:continuefor nextNode, nextDistance in graph[thisNode]:if nextDistance + thisDistance < dis[nextNode]:dis[nextNode] = nextDistance + thisDistanceway[nextNode] = way[thisNode]heapq.heappush(pq, (dis[nextNode], nextNode))elif nextDistance + thisDistance == dis[nextNode]:way[nextNode] = (way[nextNode] + way[thisNode]) % MODreturn way[-1]
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136481215
相关文章:
LeetCode 1976.到达目的地的方案数:单源最短路的Dijkstra算法
【LetMeFly】1976.到达目的地的方案数:单源最短路的Dijkstra算法 力扣题目链接:https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/ 你在一个城市里,城市由 n 个路口组成,路口编号为 0 到 n - 1 ÿ…...
vulnhub-----Hackademic靶机
文章目录 1.C段扫描2.端口扫描3.服务扫描4.web分析5.sql注入6.目录扫描7.写马php反弹shell木马 8.反弹shell9.内核提权 1.C段扫描 kali:192.168.9.27 靶机:192.168.9.25 ┌──(root㉿kali)-[~] └─# arp-scan -l Interface: eth0,…...
十秒学会Ubuntu命令行:从入门到进阶
一、引言 在使用Ubuntu操作系统时,命令行界面(CLI)是不可或缺的一部分。对于初学者来说,掌握基本的命令行操作可以帮助他们更高效地管理系统和软件。 本文将介绍一些常见的Ubuntu命令以及如何解决与命令行相关的问题。 目录 一、…...
华为智慧教室3.0的晨光,点亮教育智能化变革
“教室外有更大的世界,但世界上没有比教室更伟大的地方。” 我们在求学阶段,都听说过这句话,但往往是在走出校园之后,才真正理解了这句话。为了让走出校园的孩子能够有能力,有勇气探索广阔的世界。我们应该准备最好的教…...
深度学习预测分析API:金融领域的Game Changer
🚀 引言 在这个AI遍地开花的时代,谁能成为金融领域的真正Game Changer?那必然是是深度学习预测分析API。如大脑般高效运转的系统不仅颠覆了传统操作,更是以无与伦比的速度和精度赋予了金融数据以全新的生命。 💼 广泛…...
外贸网站做Google SEO 用wordpress模板的优势
易于优化:WordPress模板是专门为搜索引擎优化(SEO)设计的。从一开始,WordPress模板就考虑到了搜索引擎的因素,因此在构建网站时已经考虑了如何优化网站的结构和内容。使用WordPress模板可以简化优化过程,让您的网站更容易被搜索引…...
后端面试题整理-1
1.Maven 依赖传递产生版本冲突怎么解决? 升级或降级依赖版本:通过修改相关依赖的版本号,选择与项目其他依赖兼容的版本。可以通过查看 Maven 依赖树来确定哪些依赖冲突,并找出合适的版本号进行调整。排除依赖:对于特定…...
Python图像处理之光斑分析
文章目录 质心目标截取光斑半径 python图像处理教程:初步📷插值变换📷形态学处理📷滤波 光斑是工程中经常出现的图像数据,其特点是目标明确,分布清晰。对光斑图像的分析,主要包括质心定位、目标…...
软件测试 - 测试用例基本理论
1. 概念 为了特定的目的(该目的是检验代码是否满足用户需求)而设计的文档,文档包含测试输入、执行条件、预期结果等。文档的形式一般是excel表格。 比如说我们买了一台电脑,新买的笔记本检查完外观之后第一步需要查看电脑是否能够正常开机,…...
在 Flutter 中使用 flutter_gen 简化图像资产管理
你是否厌倦了在 Flutter 项目中手动管理图像资产的繁琐任务? 告别手工输入资源路径的痛苦,欢迎使用“Flutter Gen”高效资源管理的时代。在本文中,我将带您从手动处理图像资源的挫折到动态生成它们的便利。 选择1:痛苦手动添加–…...
两天学会微服务网关Gateway-Gateway过滤器
锋哥原创的微服务网关Gateway视频教程: Gateway微服务网关视频教程(无废话版)_哔哩哔哩_bilibiliGateway微服务网关视频教程(无废话版)共计17条视频,包括:1_Gateway简介、2_Gateway工作原理、3…...
图像处理 mask掩膜
1,图像算术运算 图像的算术运算有很多种,比如两幅图像可以相加,相减,相乘,相除,位运算,平方根,对数,绝对值等;图像也可以放大,缩小,旋…...
信驰达ESP32-C3/RTL8720CM WiFi开发板RF-WT01上线
为方便客户快速选型和验证WiFi模块,深圳市信驰达科技有限公司推出了WiFi开发板RF-WT01,支持适配信驰达RF-WM-ESP32B1、RF-WM-20CMB1、RF-WM-11AFB1、RF-WM-20DNB1 4款WiFi串口模块使用,方便客户实现对信驰达WiFi模块的快速测试和评估。 图1RF…...
【产品经理方法论——产品的基本概念】
1. 产品学三元素 产品学有三个元素:用户、需求、产品 产品学的内容:根据用户的需求设计产品,使用产品服务用户 仅仅通过三个元素无法说明每个元素的概念,因为三个元素互为说明关系。 通过引入人/群体来说明三个元素的关系。 需…...
推特API(Twitter API)V2 查询用户信息
前面章节已经介绍使用code换取Token的整个流程了,这里不再重复阐述了,下面我们介绍如何使用Token查询用户信息等操作。 1.引入相关依赖Maven <dependency> <groupId>oauth.signpost</groupId> <artifactId>signpost-co…...
在Elasticsearch IK分词器中更新、停用某些专有名词
在Elasticsearch IK分词器中更新、停用某些专有名词 目前IK分词器对于现有的新名词或者流行语没有做区分比如"白嫖" “奥利给”,或者对一些没有用的字比如 “的” "地"进行分词其实没有必要过多的分词只会占用宝贵的内存空间,所以如…...
时钟显示 html JavaScript
sf.html <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>时间</title><script>function showTime(){var timenew Date();var datetime.getDate();var yeartime.getFullYear();var monthtime.getMonth()1;var …...
List<Object>集合对象属性拷贝工具类
目录 问题现象: 问题分析: 解决方法: 问题现象: 最近在项目中经常会使用到BeanUtils工具类来作对象的属性字段拷贝,但如果应用到List集合的话就需要遍历去操作了,如下: 打印结果: …...
请说明Vue中的异步组件加载
Vue中的异步组件加载是指当页面需要渲染某个组件时,可以在需要时再去加载这个组件,而不是在页面初始化的时候就将所有组件一次性加载进来。这种方式能够有效降低页面的初始加载时间,提升用户体验。 在Vue中,我们可以使用import函…...
目标检测5:采用yolov8, RK3568上推理实时视频流
上一个效果图,海康球机对着电脑屏幕拍,清晰度不好。 RK3568接取RTSP视频流,通过解码,推理,编码,最终并把结果推出RTSP视频流。 数据集采用coco的80个种类集,通过从yovo8.pt,转换成R…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
