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

最短路径专题6 最短路径-多路径

题目:

样例:

输入
4 5 0 2
0 1 2
0 2 5
0 3 1
1 2 1
3 2 2

输出
2
0->1->2
0->3->2

思路:

        根据题意,最短路模板还是少不了的,

我们要添加的是,

记录各个结点有多少个上一个结点走动得来的,由于更新了最短路径,需要清空之前的记录的结点,重新记录当前结点由哪上一个结点得来的;

当遇到相同的最短路距离的时候,直接添加 j 结点也由 当前结点得来的。

最后递归遍历各个结点路径,并存储好,输出即可。

代码详解如下:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define mk make_pair
#define int long long
#define NO puts("NO")
#define YES puts("YES")
#define umap unordered_map
#define INF 0x3f3f3f3f3f3f3f3f
#define All(x) (x).begin(),(x).end()
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
using PII = pair<int,int>;int n,k,start,last;int dist[N];
bool st[N];// 建立链表
int h[N],e[N],w[N],ne[N],idx;
inline void Add(int a,int b,int c)
{e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}vector<int>tree[N];	// 记录每个结点拥有哪些结点得来的inline void Dijkstra()
{memset(dist,INF,sizeof dist);dist[start] = 0;priority_queue<PII,vector<PII>,greater<PII>>q;q.push(mk(0,start));while(q.size()){PII now = q.top();q.pop();int a = now.y;int dis = now.x;if(st[a]) continue;st[a] = true;for(int i = h[a];i != -1;i = ne[i]){int j = e[i];if(dist[j] > dis + w[i]){dist[j] = dis + w[i];tree[j].clear();	// 更新了最短路径,所以清空上一个结点记录过的多个结点 路径tree[j].emplace_back(a);	//  j 结点记录 添加 a 结点得来的路径}else // 如果遇到相同最短路距离,j 结点 添加 当前的 a 结点路径if(dist[j] == dis + w[i]) tree[j].emplace_back(a);// 记录该结点,方便下一次的走动q.push(mk(dist[j],j));}}return ;
}vector<vector<int>>paths;	// 记录多个路径
vector<int>tempPath;	// 临时路径void getPath(int now)
{// 到达递归边界,开始回溯取各个路径if(now == start){tempPath.emplace_back(now);	// 临时路径存储当前结点paths.emplace_back(tempPath);	// 存储路径tempPath.pop_back();	// 弹出存储的当前结点,进行回溯,寻找另一条不同的路径return ;}tempPath.emplace_back(now);	// 临时路径存储当前结点// 遍历 当前结点 now 由哪个结点得来的// 递归获取路径结点for(auto i : tree[now]){getPath(i);}tempPath.pop_back();	// 弹出存储的当前结点,进行回溯,寻找另一条不同的路径return ;
}inline void solve()
{// 初始化链表memset(h,-1,sizeof h);cin >> n >> k >> start >> last;while(k--){int a,b,c;cin >> a >> b >> c;Add(a,b,c);Add(b,a,c);}// 求最短路径Dijkstra();// 获取最短路径getPath(last);int sum = paths.size();	// 总的路径数量// 翻转获得的全部路径,由于我们是从终点往后获取的// 所以需要翻转一下for(int i = 0;i < sum;++i){reverse(All(paths[i]));}// 根据题意,字典序排序好每条路径sort(All(paths));// 输出路径条数cout << sum << endl;// 输出记录的每条最短路路径for(int i = 0;i < sum;++i){bool rem = false;	// 控制格式for(int j : paths[i]){if(rem) cout << "->";cout << j;rem = true;}cout << endl;}
}
signed main()
{
//	freopen("a.txt", "r", stdin);___G;int _t = 1;
//	cin >> _t;while (_t--){solve();}return 0;
}

最后提交:

相关文章:

最短路径专题6 最短路径-多路径

题目&#xff1a; 样例&#xff1a; 输入 4 5 0 2 0 1 2 0 2 5 0 3 1 1 2 1 3 2 2 输出 2 0->1->2 0->3->2 思路&#xff1a; 根据题意&#xff0c;最短路模板还是少不了的&#xff0c; 我们要添加的是&#xff0c; 记录各个结点有多少个上一个结点走动得来的…...

【Linux】Linux常用命令—文件管理(上)

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞 关注支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; &#x1f525;c系列专栏&#xff1a;C/C零基础到精通 &#x1f525; 给大…...

【Python】基于OpenCV人脸追踪、手势识别控制的求生之路FPS游戏操作

【Python】基于OpenCV人脸追踪、手势识别控制的求生之路FPS游戏操作 文章目录 手势识别人脸追踪键盘控制整体代码附录&#xff1a;列表的赋值类型和py打包列表赋值BUG复现代码改进优化总结 py打包 视频&#xff1a; 基于OpenCV人脸追踪、手势识别控制的求实之路FPS游戏操作 手…...

约束优化算法(optimtool.constrain)

import optimtool as oo from optimtool.base import np, sp, pltpip install optimtool>2.4.2约束优化算法&#xff08;optimtool.constrain&#xff09; import optimtool.constrain as oc oc.[方法名].[函数名]([目标函数], [参数表], [等式约束表], [不等式约数表], [初…...

如何查看postgresql中的数据库大小?

你可以使用以下命令来查看PostgreSQL数据库的大小&#xff1a; SELECT pg_database.datname as "database_name", pg_size_pretty(pg_database_size(pg_database.datname)) AS size_in_mb FROM pg_database ORDER by size_in_mb DESC;这将返回一个表格&#xff0…...

使用python-opencv检测图片中的人像

最简单的方法进行图片中的人像检测 使用python-opencv配合yolov3模型进行图片中的人像检测 1、安装python-opencv、numpy pip install opencv-python pip install numpy 2、下载yolo模型文件和配置文件&#xff1a; 下载地址&#xff1a; https://download.csdn.net/down…...

项目进展(三)-电机驱动起来了,发现了很多关键点,也遇到了一些低级错误,

一、前言 昨天电机没有驱动起来&#xff0c;头发掉一堆&#xff0c;不过今天&#xff0c;终于终于终于把电机驱动起来了&#xff01;&#xff01;&#xff01;&#xff01;&#xff0c;特别开心&#xff0c;哈哈哈哈&#xff0c;后续继续努力完善&#xff01;&#xff01;&…...

目标检测算法改进系列之Backbone替换为RepViT

RepViT简介 轻量级模型研究一直是计算机视觉任务中的一个焦点&#xff0c;其目标是在降低计算成本的同时达到优秀的性能。轻量级模型与资源受限的移动设备尤其相关&#xff0c;使得视觉模型的边缘部署成为可能。在过去十年中&#xff0c;研究人员主要关注轻量级卷积神经网络&a…...

学习 Kubernetes的难点和安排

Kubernetes 技术栈的特点可以用四个字来概括&#xff0c;那就是“新、广、杂、深”&#xff1a; 1.“新”是指 Kubernetes 用到的基本上都是比较前沿、陌生的技术&#xff0c;而且版本升级很快&#xff0c;经常变来变去。 2.“广”是指 Kubernetes 涉及的应用领域很多、覆盖面非…...

【MATLAB源码-第42期】基于matlab的人民币面额识别系统(GUI)。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 基于 MATLAB 的人民币面额识别系统设计可以分为以下步骤&#xff1a; 1. 数据收集与预处理 数据收集&#xff1a; 收集不同面额的人民币照片&#xff0c;如 1 元、5 元、10 元、20 元、50 元和 100 元。确保在不同环境、不…...

【软件测试】软件测试的基础概念

一、一个优秀的测试人员需要具备的素质 技能方面&#xff1a; 优秀的测试用例设计能力&#xff1a;测试用例设计能力是指&#xff0c;无论对于什么类型的测试&#xff0c;都能够设计出高效的发现缺陷&#xff0c;保证产品质量的优秀测试用例。这就需要我们掌握设计测试用例的方…...

Docker-mysql,redis安装

安装MySQL 下载MySQL镜像 终端运行命令 docker pull mysql:8.0.29镜像下载完成后&#xff0c;需要配置持久化数据到本地 这是mysql的配置文件和存储数据用的目录 切换到终端&#xff0c;输入命令&#xff0c;第一次启动MySQL容器 docker run --restartalways --name mysq…...

五种I/O模型

目录 1、阻塞IO模型2、非阻塞IO模型3、IO多路复用模型4、信号驱动IO模型5、异步IO模型总结 blockingIO - 阻塞IOnonblockingIO - 非阻塞IOIOmultiplexing - IO多路复用signaldrivenIO - 信号驱动IOasynchronousIO - 异步IO 5种模型的前4种模型为同步IO&#xff0c;只有异步IO模…...

用nativescript开发ios程序常用命令?

NativeScript是一个用于跨平台移动应用程序开发的开源框架&#xff0c;允许您使用JavaScript或TypeScript构建原生iOS和Android应用程序。以下是一些常用的NativeScript命令&#xff0c;用于开发iOS应用程序&#xff1a; 1、创建新NativeScript项目&#xff1a; tns create m…...

6.Tensors For Beginners-What are Convector

Covectors &#xff08;协向量&#xff09; What‘s a covector Covectors are “basically” Row Vectors 在一定程度上&#xff0c;可认为 协向量 基本上就像 行向量。 但不能简单地认为 这就是列向量进行转置&#xff01; 行向量 和 列向量 是根本不同类型的对象。 …...

Linux多线程网络通信

思路&#xff1a;主线程&#xff08;只有一个&#xff09;建立连接&#xff0c;就创建子线程。子线程开始通信。 共享资源&#xff1a;全局数据区&#xff0c;堆区&#xff0c;内核区描述符。 线程同步不同步需要取决于线程对共享资源区的数据的操作&#xff0c;如果是只读就不…...

矩阵的c++实现(2)

上一次我们了解了矩阵的运算和如何使用矩阵解决斐波那契数列&#xff0c;这一次我们多看看例题&#xff0c;了解什么情况下用矩阵比较合适。 先看例题 1.洛谷P1939 【模板】矩阵加速&#xff08;数列&#xff09; 模板题应该很简单。 补&#xff1a;1<n<10^9 10^9肯定…...

RPC 框架之Thrift入门(一)

&#x1f4cb; 个人简介 &#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是阿牛&#xff0c;全栈领域优质创作者。&#x1f61c;&#x1f4dd; 个人主页&#xff1a;馆主阿牛&#x1f525;&#x1f389; 支持我&#xff1a;点赞&#x1f44d;收藏⭐️留言&#x1f4d…...

【C++】运算符重载 ⑥ ( 一元运算符重载 | 后置运算符重载 | 前置运算符重载 与 后置运算符重载 的区别 | 后置运算符重载添加 int 占位参数 )

文章目录 一、后置运算符重载1、前置运算符重载 与 后置运算符重载 的区别2、后置运算符重载添加 int 占位参数 上 2 2 2 篇博客 【C】运算符重载 ④ ( 一元运算符重载 | 使用 全局函数 实现 前置 自增运算符重载 | 使用 全局函数 实现 前置 - - 自减运算符重载 )【C】运算符…...

538. 把二叉搜索树转换为累加树

题目描述 给出二叉 搜索 树的根节点&#xff0c;该树的节点值各不相同&#xff0c;请你将其转换为累加树&#xff08;Greater Sum Tree&#xff09;&#xff0c;使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下&#xff0c;二叉搜索树满足下列约束…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...