当前位置: 首页 > news >正文

最短路的方案数+打印路径

这个题目整合了我们最短路用到的很多技能
如何统计最短路径的方案数呢,这就需要我们另外开一个全局数组
如何打印路径呢,还是开一个全局的数组,记录前一个是啥就行

简单的来说,要增加啥新的功能,直接多开全局变量就行,没必要写在优先队列里面,不好转换


题目地址

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;const int N = (int)505;
int n,m,s,d;
int num[N];
// 没有说明有多少条边
struct node{int v,w;
};vector<node> ed[N];
vector<int> path(N,-1);vector<int> cnt(N,0);
vector<int> shu(N,0);void fun(){vector<int> dis(n,0x3f3f3f3f);vector<int> vis(n,0);priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;q.push({0,s});cnt[s] = 1;shu[s] = num[s];dis[s] = 0;while(q.size()){auto now = q.top();q.pop();int d = now.first, u = now.second;if(vis[u]) continue;vis[u] = 1;for(int i=0;i<ed[u].size();i++){int v = ed[u][i].v, w = ed[u][i].w;if(d+w<dis[v]){   // 这里还是很正常的最短路dis[v] = d + w;cnt[v] = cnt[u];shu[v] = shu[u] + num[v];path[v] = u;q.push({dis[v],v});}else if(d+w==dis[v]){   // 如果距离相等就需要加上这条路径上的方案数cnt[v] += cnt[u];if(shu[v]<shu[u]+num[v]){  // 相同距离下,如果救援队的数量更多,就采取这条新的路径path[v] = u;shu[v] = shu[u] + num[v];}}}}}int main(){cin >> n >> m >> s >> d;for(int i=0;i<n;i++){cin >> num[i];}int u,v,w;for(int i=1;i<=m;i++){cin>>u>>v>>w;ed[u].push_back({v,w});ed[v].push_back({u,w});}fun();cout << cnt[d] << " " << shu[d] << endl;vector<int> ans;int now = d;while(path[now]!=-1){ans.push_back(path[now]);now = path[now];}for(int i=ans.size()-1;i>=0;i--){cout << ans[i] << " ";}cout << d;return 0;
} 

要弄清楚的就是距离相同的时候,如何进行转换,距离相同的时候,救援队的数量就是我们需要考虑的因素,我们直接采取新的路径就行

可能有的疑惑是为什么路径相等的时候不再次将这个节点push到堆中,这是因为我们的堆中肯定存在这个节点了,且一定没有遍历到,这是因为我们的当前的距离是d , 而v节点的距离dis[v] == d + w,这么说dis[v]大于d,那么v节点一定存在于堆中,我们就没必要重复push进去了

相关文章:

最短路的方案数+打印路径

这个题目整合了我们最短路用到的很多技能 如何统计最短路径的方案数呢&#xff0c;这就需要我们另外开一个全局数组 如何打印路径呢&#xff0c;还是开一个全局的数组&#xff0c;记录前一个是啥就行 简单的来说&#xff0c;要增加啥新的功能&#xff0c;直接多开全局变量就行…...

Python爬虫系列教程之第十三篇:构建高可用爬虫系统 —— 混合架构与自动化监控

大家好&#xff0c;欢迎继续关注本系列爬虫教程&#xff01;随着爬虫项目规模的不断扩大和业务需求的提升&#xff0c;单一技术方案往往难以满足实际应用中对高可用性、稳定性和自动化监控的要求。如何构建一个既能应对多种反爬策略&#xff0c;又能在异常情况下自动恢复、实时…...

Python学习心得浅拷贝与深拷贝

一、变量的赋值、浅拷贝以及深拷贝的定义&#xff1a; 1.变量的赋值&#xff1a;只是形成两个变量&#xff0c;实际上还是指向同一个对象 2.浅拷贝&#xff1a;拷贝时&#xff0c;对象包含的子对象内容不拷贝&#xff0c;因此&#xff0c;源对象与拷贝对象会引用同一个子对象…...

cs106x-lecture13(Autumn 2017)-SPL实现

打卡cs106x(Autumn 2017)-lecture13 (以下皆使用SPL实现&#xff0c;非STL库&#xff0c;后续课程结束会使用STL实现) 1、v1v2p1p2 The following code C uses pointers and produces two lines of output. What is the output? int v1 10; int v2 25; int* p1 &v1…...

3D模型在线转换工具:轻松实现3DM转OBJ

3D模型在线转换是一款功能强大的在线工具&#xff0c;支持多种3D模型格式的在线预览和互转。无论是工业设计、建筑设计&#xff0c;还是数字艺术领域&#xff0c;这款工具都能满足您的需求。 3DM与OBJ格式简介 3DM格式&#xff1a;3DM是一种广泛应用于三维建模的文件格式&…...

AI IDE 新势力 Trae 功能深度解析:Builder与Chat模式的应用场景与市场竞争力分析

文章目录 一、前言二、简介2.1 Trae 的背景与定位 三、Trae 核心功能3.1 Builder模式介绍3.2 Chat模式介绍 四、Trae 实际应用案例4.1 Trae 安装与配置4.1.1 Trae 安装与配置4.1.2 Trae 设置 4.2 实战案例分享4.2.1 Trae Builder模式&#xff1a;从0到1生成对接 DeepSeek 的聊天…...

天 锐 蓝盾终端安全管理系统:办公U盘拷贝使用管控限制

天 锐 蓝盾终端安全管理系统以终端安全为基石&#xff0c;深度融合安全、管理与维护三大要素&#xff0c;通过对桌面终端系统的精准把控&#xff0c;助力企业用户构筑起更为安全、稳固且可靠的网络运行环境。它实现了管理的标准化&#xff0c;有效破解终端安全管理难题&#xf…...

ADCP处理软件CODAS安装 (conda方法安装)

夏威夷大学出品的ADCP处理软件&#xff0c;我主要用来查看船载ADCP流速数据。 1. 先安装conda(miniconda就可以)&#xff0c;这里不再赘述&#xff0c;安装完可以添加conda库和取消登录自动激活conda conda config --add channels conda-forge # 添加库 conda config --set a…...

JUC并发—9.并发安全集合三

大纲 1.并发安全的数组列表CopyOnWriteArrayList 2.并发安全的链表队列ConcurrentLinkedQueue 3.并发编程中的阻塞队列概述 4.JUC的各种阻塞队列介绍 5.LinkedBlockingQueue的具体实现原理 6.基于两个队列实现的集群同步机制 1.并发安全的数组列表CopyOnWriteArrayList …...

后端Java Stream数据流的使用=>代替for循环

API讲解 对比 示例代码对比 for循环遍历 package cn.ryanfan.platformback.service.impl;import cn.ryanfan.platformback.entity.Algorithm; import cn.ryanfan.platformback.entity.AlgorithmCategory; import cn.ryanfan.platformback.entity.DTO.AlgorithmInfoDTO; im…...

强化学习-GAE方法

2016-ICLR-HIGH-DIMENSIONAL CONTINUOUS CONTROL USING GENERALIZED ADVANTAGE ESTIMATION 解决问题 强化学习的目标为最大化策略的预期总回报&#xff0c;其中一个主要困难为 行为对reward的影响存在一个长时间的延迟&#xff08;credit assignment problem&#xff09;。价…...

51c大模型~合集71

我自己的原文哦~ https://blog.51cto.com/whaosoft/12260659 #大模型推理加速技术的学习路线 EfficientQAT 可以在 41 小时内在单个 A100-80GB GPU 上完成对 2-bit Llama-2-70B 模型的量化感知训练。与全精度模型相比&#xff0c;精度仅下降了不到 3%&#xff08;69.48 v…...

PyTorch-基础(CUDA、Dataset、transforms、卷积神经网络、VGG16)

PyTorch-基础 环境准备 CUDA Toolkit安装&#xff08;核显跳过此步骤&#xff09; CUDA Toolkit是NVIDIA的开发工具&#xff0c;里面提供了各种工具、如编译器、调试器和库 首先通过NVIDIA控制面板查看本机显卡驱动对应的CUDA版本&#xff0c;如何去下载对应版本的Toolkit工…...

Linux(centos)系统安装部署MySQL8.0数据库(GLIBC版本)

安装前检查服务器glibc版本&#xff0c;下载对应版本包 rpm -qa | grep glibc mysql安装包及依赖包已整理好&#xff0c;下载地址&#xff1a;https://pan.quark.cn/s/3137acc814c0&#xff0c;下载即可安装 一、下载MySQL mysql安装包及依赖包已整理好&#xff0c;下载地址…...

Transformer解析——(四)Decoder

本系列已完结&#xff0c;全部文章地址为&#xff1a; Transformer解析——&#xff08;一&#xff09;概述-CSDN博客 Transformer解析——&#xff08;二&#xff09;Attention注意力机制-CSDN博客 Transformer解析——&#xff08;三&#xff09;Encoder-CSDN博客 Transforme…...

TypeScript 中 type 和 interface 深度对比分析

一、核心概念对比 特性interfacetype本质声明式类型契约&#xff08;面向对象范式&#xff09;类型别名&#xff08;函数式编程思维&#xff09;可扩展性支持声明合并&#xff08;多次声明自动合并&#xff09;不可合并基础类型支持只能描述对象/函数类型可描述任意类型&#…...

unplugin-vue-components,unplugin-auto-import,借用ai去学习

好的&#xff0c;我现在需要帮助用户理解他们提供的这段Vite配置代码。用户之前已经询问过关于ElementPlusResolver的导入问题&#xff0c;现在他们展示了在vite.config.ts中使用该解析器的具体配置。我需要逐步分析这段代码&#xff0c;并解释每个部分的作用。 首先&#xff…...

Nginx学习笔记:常用命令端口占用报错解决Nginx核心配置文件解读

Nginx 1. 基础命令1.1 重新加载systemd配置1.2 停止Nginx服务1.3 启动Nginx服务1.4 重启Nginx服务1.5 查看Nginx服务状态1.6 测试配置和重载Nginx 2. 额外命令2.1 启用开机自启2.2 禁用开机自启2.3 强制关闭所有Nginx进程 3. Nginx端口占用解决方案3.1 查找占用端口8090的进程3…...

C++ ——继承

体现的是代码复用的思想 1、子类继承父类&#xff0c;子类就拥有了父类的特性&#xff08;成员方法和成员属性&#xff09; 2、已存在的类被称为“基类”或者“父类”或者“超类”&#xff1b;新创建的类被称为“派生类”或者“子类” 注意&#xff1a; &#xff08;1&#…...

正则表达式常用记录

1. 定义 正则表达式&#xff0c;又称规则表达式,&#xff08;Regular Expression&#xff0c;在代码中常简写为regex、regexp或RE&#xff09;&#xff0c;它是一种文本模式&#xff0c;同时也是计算机科学的一个概念&#xff0c;其中包括普通字符&#xff08;例如&#xff0c…...

redis的应用,缓存,分布式锁

1.应用 1.1可以用作缓存 作用&#xff1a;提交数据的查询效率&#xff0c;减少对数据库的访问频率 什么数据适合放入缓存 1.查询频率高&#xff0c;修改频率低 2.对安全系数比较低 如何实现 Service public class DeptServer {Autowiredprivate DeptMapper deptMapper;Auto…...

qt5实现表盘的旋转效果,通过提升QLabel类

因为工作需要&#xff0c;需要实现温度的表盘展示效果 实现思路&#xff1a; 通过提示声QLabel控价类&#xff0c;实现报盘的旋转和展示效果 1. 编写一个QLabel的类MyQLabel,实现两个方法 1. void paintEvent(QPaintEvent *event); //重绘函数 2. void valueChanged(int va…...

Flutter项目中设置安卓启动页

AndroidManifest.xml 设置 android:theme“style/LaunchTheme” <applicationandroid:label"string/app_name"android:name"${applicationName}"android:icon"mipmap/ic_launcher"android:roundIcon"mipmap/ic_launcher"android:t…...

人工智能之目标追踪DeepSort源码解读(yolov5目标检测,代价矩阵,余弦相似度,马氏距离,匹配与预测更新)

要想做好目标追踪,须做好目标检测,所以这里就是基于yolov5检测基础上进行DeepSort,叫它为Yolov5_DeepSort。整体思路是先检测再追踪,基于检测结果进行预测与匹配。 一.参数与演示 这里用到的是coco预训练人的数据集&#xff1a; 二.针对检测结果初始化track 对每一帧数据都输出…...

C语言之枚举类型

目录 前言 一、enum&#xff08;枚举 总结 前言 在C语言中&#xff0c;枚举类型是一种用户自定义的数据类型&#xff0c;用于定义一组具名的常量集合。枚举类型可以提高代码的可读性和可维护性&#xff0c;同时也能够帮助程序员避免使用魔法数字。通过枚举类型&#xff0c;我们…...

【Python爬虫(12)】正则表达式:Python爬虫的进阶利刃

【Python爬虫】专栏简介&#xff1a;本专栏是 Python 爬虫领域的集大成之作&#xff0c;共 100 章节。从 Python 基础语法、爬虫入门知识讲起&#xff0c;深入探讨反爬虫、多线程、分布式等进阶技术。以大量实例为支撑&#xff0c;覆盖网页、图片、音频等各类数据爬取&#xff…...

推荐一款AI大模型托管平台-OpenWebUI

推荐一款AI大模型托管平台-OpenWebUI 1. OpenWebUI 1. OpenWebUI什么? 官网地址&#xff1a;https://openwebui.com/ GitHub地址&#xff1a; https://github.com/open-webui/open-webui Open WebUI 是一个可扩展、功能丰富且用户友好的自托管 AI 平台&#xff0c;旨在完全离…...

复习dddddddd

1. 思路&#xff1a;用队列先进先出的特性 #include <iostream> #include <vector> #include <stack> #include <cstdio> #include <algorithm> #include <cstring> #include <climits> #include <cstdlib> #include <cma…...

【3.5JavaScript】JavaScript字符串对象

文章目录 1.获取字符串长度2.大小写转换3.获取某一个字符4.截取字符串5.替换字符串6.分割字符串7.检索字符串位置8.例题&#xff1a;统计某一个字符的个数 在 JavaScript 中&#xff0c;对象是非常重要的知识点。对象分为两种&#xff1a;一种是 ”自定义对象“&#xff0c;另…...

消息队列-持续更新中

消息队列 0、消息队列官方参考文档 MQ官方参考文档 RocketMQ 官方文档&#xff1a; https://rocketmq.apache.org/docs/quick-start/ RocketMQ 中国开发者中心&#xff1a;http://rocketmq.cloud/zh-cn/ Kafka 官方文档&#xff1a; http://kafka.apache.org/documentation/ …...

创建一个简单的spring boot+vue前后端分离项目

一、环境准备 此次实验需要的环境&#xff1a; jdk、maven、nvm和node.js 开发工具&#xff1a;idea或者Spring Tool Suite 4&#xff0c;前端可使用HBuilder X&#xff0c;数据库Mysql 下面提供maven安装与配置步骤和nvm安装与配置步骤&#xff1a; 1、maven安装与配置 1…...

已知点矩阵的三个顶点坐标、行列数和行列的间距,计算得出剩余所有点的坐标

已知点矩阵的三个顶点坐标、行列数和行列的间距&#xff0c;计算得出剩余所有点的坐标 计算矩阵中每个点的坐标代码实现案例图调用验证 计算矩阵中每个点的坐标 给定左上角、左下角和右上角三个点的坐标&#xff0c;以及矩阵的行数、列数、行间距和列间距&#xff0c;我们可以…...

视频mp4垂直拼接 水平拼接

视频mp4垂直拼接 水平拼接 pinjie_v.py import imageio import numpy as np import os import cv2def pinjie_v(dir1,dir2,out_dir):os.makedirs(out_dir, exist_okTrue)# 获取目录下的所有视频文件video_files_1 [f for f in os.listdir(dir1) if f.endswith(.mp4)]video_fi…...

【记录54】渐变色 linear-gradient / radial-gradient

linear-gradient 线性渐变&#xff1a;是以直线条渐变 radial-gradient 径向渐变&#xff1a;是以图型形状渐变 <!-- 线性渐变&#xff08;从一个方向到另一个方向 --><div style" background: linear-gradient(to right, red, blue);"></div><…...

一周学会Flask3 Python Web开发-response响应格式

锋哥原创的Flask3 Python Web开发 Flask3视频教程&#xff1a; 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 在HTTP响应中&#xff0c;数据可以通过多种格式传输。大多数情况下&#xff0c;我们会使用HTML格式&#xff0c;这也是Flask中…...

二级公共基础之数据结构与算法篇(八)排序技术

目录 前言 一、交换类排序 1.冒泡排序法 1. 冒泡排序的思想 2. 冒泡排序的实现步骤 3. 示例 4. 冒泡排序的特点 2.快速排序 1. 快速排序的核心思想 2. 快速排序的实现步骤 3. 示例代码(C语言) 4. 快速排序的特点 二、插入类排序 1. 简单插入排序 1.简单插入排…...

以ChatGPT为例解析大模型背后的技术

目录 1、大模型分类 2、为什么自然语言处理可计算&#xff1f; 2.1、One-hot分类编码&#xff08;传统词表示方法&#xff09; 2.2、词向量 3、Transformer架构 3.1、何为注意力机制&#xff1f; 3.2、注意力机制在 Transformer 模型中有何意义&#xff1f; 3.3、位置编…...

Ubuntu 下 nginx-1.24.0 源码分析 - ngx_cpuinfo 函数

ngx_cpuinfo 声明在 src/core/ngx_core.h void ngx_cpuinfo(void); 定义在 src/core/ngx_cpuinfo.c 这里 ngx_cpuinfo 的定义可以找到 2 个 使用 gcc -E 处理一下来确认当下环境中使用的是哪一个 gcc -E src/core/ngx_cpuinfo.c \-I src/core \-I src/event \-I src/event/modu…...

python小项目编程-中级(1、图像处理)

目录 图像处理 实现 测试 unittest pytest 图像处理 实现界面化操作&#xff0c;使用PIL库实现简单的图像处理功能&#xff0c;如缩放&#xff08;设置缩放比例&#xff09;、旋转和滤镜、对比度调整、亮度调整、灰度图、二值化图&#xff08;二值图如果使用的是彩色图片需…...

EasyExcel实现excel导入(模版上传)

目录 效果pom.xmlapplication.ymlcontrollerservice依赖类前台vue代码某个功能如果需要添加大量的数据,通过一条条的方式添加的方式,肯定不合理,本文通过excel导入的方式来实现该功能,100条数据导入成功85条,失败15条,肯定需要返回一个表格给前台或者返回1个错误excel给前…...

AI工作流+专业知识库+系统API的全流程任务自动化

我有点悲观&#xff0c;甚至很沮丧&#xff0c;因为AI留给普通人的机会不多了&#xff0c;这既是人类之间权力的斗争&#xff0c;也是硅基生命和碳基生命的斗争。AI自动化是无法避免的趋势&#xff0c;如果人类不能平权&#xff0c;那就只能跪下接受审判。 通过整合AI工作流、专…...

【C/C++】合并两个有序链表 (leetcode T21)

核心考点预览&#xff1a;链表 &#xff08;双指针&#xff09; 技巧&#xff1a;虚拟头结点 题目描述&#xff1a; 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例&#xff1a; 输入输出示例1l1 [1,2,4], l2 [1…...

C语言进阶习题【2】(4结构体进阶)——通讯录的实现3

1. 本节在动态版本通讯录的基础上实现存储功能 在动态版本的基础上&#xff0c;对于通讯录的新增了存储到文件中&#xff0c;可以从文件中打开我们存储的通信录功能。新增函数&#xff1a;saveContatc()和loadContact&#xff08;&#xff09; 2. 具体实现 2.1 contact.h /…...

Linux系统编程之无名管道

概述 在Linux系统中&#xff0c;无名管道是一种简单的进程间通信机制。它允许一个进程创建一对文件描述符&#xff0c;其中一个用于读取&#xff0c;另一个用于写入。当一个进程通过系统调用创建了一个无名管道后&#xff0c;便可以将这两个文件描述符传递给它的子进程&#xf…...

deepseek与其他大模型配合组合

DeepSeek与其他大模型的配合组合&#xff0c;展现了其在多个领域中的强大应用潜力和灵活性。以下是对DeepSeek与其他大模型配合组合的详细分析&#xff1a; 一、DeepSeek与华知大模型的组合 背景介绍&#xff1a; 华知大模型是同方知网与华为联手打造的&#xff0c;具备全学科…...

ASP.NET Core Clean Architecture

文章目录 项目地址一、1. 重点1.1 Repository数据库接口1.2 GetEventDetail 完整的Query流程1.3 创建Command并使用validation 项目地址 教程作者&#xff1a;ASP.NET Core Clean Architecture 2022-12 教程地址&#xff1a; https://www.bilibili.com/video/BV1YZ421M7UA?…...

DeepSeek安装部署笔记(一)

Ollamaopen-WebUI部署 DeepSeek安装部署笔记第一步 Ollama安装1.安装ollama&#xff1a;官网https://ollama.com/下载2.上面安装完成&#xff0c;在cmd命令行&#xff1a; 第二步 给DeepSeek添加OpenWebUI界面&#xff08;重点&#xff09;1.安装conda&#xff1a;用它来管理py…...

ProfiNet转EtherNet/IP罗克韦尔PLC与监控系统通讯案例

一、案例背景 在新能源产业蓬勃发展的当下&#xff0c;大型光伏电站作为绿色能源的重要输出地&#xff0c;其稳定高效的运行至关重要。某大型光伏电站占地面积广阔&#xff0c;内部设备众多&#xff0c;要保障电站的稳定运行&#xff0c;对站内各类设备进行集中监控与管理必不可…...

23.2 HtmlDocument类

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 HtmlDocument类提供了HTML文档的顶级编程访问&#xff0c;配合WebBrowser的 Document属性使用&#xff0c;可以获得WebBrowser当前页…...

wordpress adrotate插件 文件上传漏洞

当你爆破进wordpress后台但权限不是管理员的时&#xff0c;如果你有adrotate插件操作权限可以用adrotate的文件上传功能get webshell 该漏洞需要AdRotate版本 < 5.13.3 第一步按顺序点击上传文件 在这里文件一定要压缩成zip格式&#xff0c;上传的时候也是上传这个zip 上…...