使用图论技巧——有遍数限制的最短路
给定一个 n个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出从 11 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。
注意:图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行,每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边,边长为 z。
点的编号为 1∼n。
输出格式
输出一个整数,表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径,则输出 impossible。
数据范围
1≤n,k≤500
1≤m≤10000
1≤x,y≤n
任意边长的绝对值不超过 10000。
输入样例:
3 3 1
1 2 1
2 3 1
1 3 3
输出样例:
3
Bellman - ford 算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在 n-1 次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。
(通俗的来讲就是:假设 1 号点到 n 号点是可达的,每一个点同时向指向的方向出发,更新相邻的点的最短距离,通过循环 n-1 次操作,若图中不存在负环,则 1 号点一定会到达 n 号点,若图中存在负环,则在 n-1 次松弛后一定还会更新)
对于含有负权边的问题,不能使用dijkstra进行求解
代码演示:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 550,M = 100010;
int n,m,k;
int dist[N],backup[N];// backup数组是复制上一次dist数组中的值 struct Edge
{int a,b,w;
} edge[M];void bellman_ford()
{memset(dist,0x3f,sizeof dist);dist[1] = 0;for(int i=0;i<k;i++){//备份数组的作用是防止串联,//串联这个词可能很抽象很多人不理解,我们考虑这样一个场景,//在一次迭代中 我们分别更新dist[2]dist[3] 2->3,如果我们直接使用dist数组进行更新,//那么dist[3]就会用 更新过的dist[2] 来更新dist[3],这里实际上是 dist[1] + w(1, 2) + w(2, 3),//这意味着我们使用了两条边来更新dist[3],这是不符合要求的,所以我们需要备份数组来确保每次迭代只会使用一条边来更新 dist数组,//这样每次更新使用的边数就在我们的可控范围之内。//通过使用备份数组,我们每次迭代 都会比上一次多使用一条边,是逐次增加的,最后我们就可以得到最大使用k条边的结果memcpy(backup,dist,sizeof dist);for(int j=0;j<m;j++){int a = edge[j].a,b = edge[j].b,w = edge[j].w;dist[b] = min(dist[b],backup[a]+w);}}}int main(void)
{// n 是图中的点数,m 是总共的边数,k 是限制的路径数 scanf("%d%d%d",&n,&m,&k);for(int i=0;i<m;i++){int a,b,w;scanf("%d%d%d",&a,&b,&w);edge[i] = {a,b,w};}bellman_ford();// 这里是因为如果存在负权边是,则不会有更新操作 if(dist[n]> 0x3f3f3f3f/2) puts("impossible");else printf("%d\n",dist[n]);return 0;
}
相关文章:
使用图论技巧——有遍数限制的最短路
给定一个 n个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。 请你求出从 11 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。 注意:图中可能 存在负权回路…...
flume 使用 exec 采集容器日志,转储磁盘
flume 使用 exec 采集容器日志,转储磁盘 在该场景下,docker 服务为superset,flume 的sources 选择 exec , sinks选择 file roll 。 任务配置 具体配置文件如下: #simple.conf: A single-node Flume configuration#…...
459重复的子字符串
给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。 public repeatedSubstringPattern(String s){int n s.length();for(int i 1; i < n / 2; i){if(n % i ! 0) continue;// substring获取子字符串是左闭右开的String ss s.substring(0,…...
【HarmonyOS NEXT】实现截图功能
【HarmonyOS NEXT】实现截图功能 【需求】 实现:实现点击截图按钮,实现对页面/组件的截图 【步骤】 编写页面UI Entry Component struct Screenshot {BuildergetSnapContent() {Column() {Image().width(100%).objectFit(ImageFit.Auto).borderRadi…...
小皮面板webman ai项目本地启动教程
1.前置条件 下载小皮面板 下载后,双击安装,一路next(下一步),无需更改配置。 2.安装必须软件 在小皮面板的软件管理页,安装编号①②③④下面四个软件。 3.启动本地服务 进入到小皮面板的首页&#x…...
从零实现诗词GPT大模型:实现多头自注意力
专栏规划: https://qibin.blog.csdn.net/article/details/137728228 在上一篇文章的最后,我们已经介绍了为什么要使用多头注意力了,本篇文章我们主要来实现多头自注意力,然后综合我们之前实现的FFN和TransformerBlock其实就差不多完成了整个GPT模型的实现了。 在开始实现之…...
[rk3399 android11]关闭声卡
使用以下命令查看声卡,可以看到目前有三个声卡 cat /proc/asound/cards 修改设备树 diff --git a/kernel/arch/arm64/boot/dts/rockchip/rk3399-jw-d039.dts b/kernel/arch/arm64/boot/dts/rockchip/rk3399-jw-d039.dtsindex 515334c127..5b592a852f 100755--- a/…...
项目实战 ---- 商用落地视频搜索系统(7)---预处理二次优化
目录 背景 要解决的问题 技术理念与落地思路 完整代码 另外的问题与解决 优化运行效果 log 效果图 背景 作为商用落地系统,我们当然希望搜索视频的关联度或者说准确性与我们希望查询的视频相关度越高越好。为此,除了在query 层面上优化,我们还需要注重我们的录入数…...
【干货分享】央企国企的群面、半结构面试复习方法和经验总结
目录 0.前言1.个人背景介绍2.行业选择心路历程3.求职历程3.1 网申如何准备?3.2 笔试考什么?如何准备3.2.1 笔试考什么?3.2.2 笔试如何准备4.面试如何准备?敲黑板!重点!4.1 面试题收集来源、我的准备方法4.…...
前端HTML基础笔记
HTML(HyperText Markup Language,超文本标记语言)是一种用于创建网页的标准标记语言。它通过一系列的元素(或称为标签)来定义网页的结构和内容。HTML文档由一系列的元素组成,这些元素可以包含文本、图片、链…...
用三极管搭建简易电流源
目录 一、三极管搭建电流源设计思路二、实例及搭建仿真1.电阻分压偏置 2.齐纳二极管偏置 3.串联二极管偏置 一、三极管搭建电流源设计思路 设计思路:利用分压电路,可用多种方式给基极提供偏压,使三极管处于放大区,VB保持稳定电压&…...
MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源
项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥…...
Android Google Maps
Android 谷歌地图 前言正文一、设置Google Cloud 项目二、项目配置① 设置SDK② 配置API密钥③ 配置AndroidManifest.xml 三、添加地图四、定位当前① 请求定位权限② 我的位置控件③ 获取当前位置 五、配置地图① xml配置地图② 代码配置地图③ 地图点击事件④ 管理Marker 六、…...
Linux——进程概念
什么是操作系统 操作系统管理各种计算机硬件、为应用程序提供基础、并且充当计算机硬件与用户之间的中介。 冯诺依曼体系 这里的存储器指的是内存不考虑缓存情况,这里的CPU能且只能对内存进行读写,不能访问外设(输入或输出设备)外设(输入或输出设备)要…...
【H2O2|全栈】关于HTML(1)认识HTML
HTML相关知识 目录 前言 准备工作 WEB前端是什么? HTML是什么? 如何运行HTML文件? 标签 概念 分类 双标签和单标签 行内标签和块标签 HTML文档结构 预告和回顾 UI设计相关 Markdown | Md文档相关 项目合作管理相关 后话 前…...
Oracle(111) 如何使用RMAN备份数据库?
使用 RMAN(Recovery Manager)备份 Oracle 数据库是确保数据安全和可恢复性的关键步骤。下面是详细的指导和代码示例,展示如何使用 RMAN 进行数据库备份。 1. 准备工作 在开始备份之前,需要确保以下几点: 已安装并配…...
linux字符设备驱动程序
字符设备驱动程序简介 linux系统中万物皆文件,驱动程序加载后会在/dev目录下生成一 个对应的文件,如/dev/led。应用程序就是先用open打开该文件, 用write控制led的亮灭,用read读取led的亮灭,用完之后用close 关闭该…...
【pyhton】python如何实现将word等文档中的文字转换成语音
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,…...
Claude Enterprise推出计划
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
【前端】CSS控制style样式失效
在CSS中,可以通过几种方式控制或禁用特定的style样式。 使用all: unset来重置所有可继承的属性,并清除所有的样式: .element {all: unset;} 使用inherit值来使属性获取其父元素的值: .element {color: inherit;font-size: inh…...
医疗AI智能体:从数据到关怀人文设计:告别冰冷精准,构建有温度的诊疗交互.131
一、智能体的人文设计医疗AI智能体以大模型为核心,串联医学知识图谱、实体识别模块、风险评估模块、话术生成模块、伦理审核模块五大核心组件,最终实现精准医学判断 人性化交互的双重目标。而在医疗场景中,用户的核心需求从来不是单纯的数据…...
Java开发必看:解决国密SM2算法报错‘Unknown named curve‘的完整指南(附Bouncy Castle配置)
Java开发实战:国密SM2算法Unknown named curve报错深度解析与Bouncy Castle最佳配置指南 金融级Java应用开发中,国密算法SM2的集成就像在钢筋森林里铺设光纤——看似简单却暗藏技术陷阱。当控制台突然抛出Unknown named curve: 1.2.156.10197.1.301这个看…...
在ESP32上为LVGL 8.x添加中文输入法:从拼音到候选词显示的完整实现
在ESP32上为LVGL 8.x实现高性能中文输入法的工程实践 当我们在智能家居控制面板上输入Wi-Fi密码时,或者在工业HMI设备中输入参数时,中文输入往往成为嵌入式设备最令人头疼的用户体验瓶颈。ESP32作为物联网领域的主流芯片,其有限的RAM资源&…...
Z-Image-Turbo模型在智能车领域的应用:仿真场景图像生成
Z-Image-Turbo模型在智能车领域的应用:仿真场景图像生成 最近和几个做自动驾驶算法的朋友聊天,他们都在为一个问题头疼:测试数据不够用。特别是那些罕见的极端场景,比如暴雨天、浓雾夜,或者刺眼的逆光路况,…...
影墨·今颜GPU算力适配:RTX 4090单卡实测每秒1.8张1024x1536图
影墨今颜GPU算力适配:RTX 4090单卡实测每秒1.8张1024x1536图 1. 引言:当顶级AI影像遇上顶级显卡 如果你是一位内容创作者,或者对AI生成人像有浓厚兴趣,那么“影墨今颜”这个名字最近可能已经进入了你的视野。它被描述为一款融合…...
Phi-4-mini-reasoning步骤详解:supervisorctl管理服务全命令解析
Phi-4-mini-reasoning步骤详解:supervisorctl管理服务全命令解析 1. 项目介绍 Phi-4-mini-reasoning是一款由微软开发的3.8B参数轻量级开源模型,专为数学推理、逻辑推导和多步解题等强逻辑任务设计。该模型主打"小参数、强推理、长上下文、低延迟…...
Python中CSV文件处理的常见累积错误及修正方案
在使用 Python 的 csv 模块处理学生成绩数据时,一个极易被忽视却影响结果准确性的典型问题是变量作用域与重用逻辑错误。如原始代码所示,grades [] 被定义在 for row in reader: 循环外部,导致每次迭代都将新学生的成绩追加到同一个列表中—…...
LFM2.5-1.2B-Thinking-GGUF部署教程:Ubuntu/CentOS/Debian三平台通用安装步骤
LFM2.5-1.2B-Thinking-GGUF部署教程:Ubuntu/CentOS/Debian三平台通用安装步骤 1. 平台简介 LFM2.5-1.2B-Thinking-GGUF是Liquid AI推出的轻量级文本生成模型,特别适合在资源有限的环境中快速部署。该镜像内置了GGUF模型文件和llama.cpp运行时ÿ…...
YOLOv8模型在RKNN平台上的实战部署指南(附完整代码)
YOLOv8模型在RKNN平台上的实战部署指南(附完整代码) 在嵌入式设备上部署高性能目标检测模型一直是计算机视觉领域的难点。瑞芯微(Rockchip)推出的RKNN推理框架为这一挑战提供了解决方案,尤其适合需要低功耗、高效率的边…...
7步掌握MetaGPT:从单行需求到完整软件的多智能体革命
7步掌握MetaGPT:从单行需求到完整软件的多智能体革命 【免费下载链接】MetaGPT 🌟 The Multi-Agent Framework: First AI Software Company, Towards Natural Language Programming 项目地址: https://gitcode.com/GitHub_Trending/me/MetaGPT 想…...
