52、有边数限制的最短路
有边数限制的最短路
题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible。
注意:图中可能 存在负权回路 。
输入格式
第一行包含三个整数n,m,k。
接下来m行,每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。
输出格式
输出一个整数,表示从1号点到n号点的最多经过k条边的最短距离。
如果不存在满足条件的路径,则输出“impossible”。
数据范围
1 ≤ n , k ≤ 500 , 1≤n,k≤500, 1≤n,k≤500,
1 ≤ m ≤ 10000 , 1≤m≤10000, 1≤m≤10000,
任意边长的绝对值不超过10000。
输入样例:3 3 1
1 2 1
2 3 1
1 3 3输出样例:3
Solution
Bellman-Ford算法
时间复杂度 O ( n m ) O(nm) O(nm), n 表示点数,m 表示边数
一般 spfa 性能比 Bellman-Ford 好,只有特殊情况下用 Bellman-Ford 算法,比如这题有边的数量的限制
- 思路
for n 次for 所有边 a,b,wdist[b] = min(dist[b], dist[a] + w)
- 解题代码
import java.util.*;
import java.io.*;class Main{// 稀疏图用邻接表来存储static int N = 510;static int M = 10010;// 存储所有边static Node[] e = new Node[M];// 存储距离起点的距离static int[] d = new int[N];// 备份 d 数组static int[] b = new int[N];static int idx = 1;// 初始化值static final int INF = 0x3f3f3f3f;public static void main(String[] args) throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] s = br.readLine().split(" ");int n = Integer.parseInt(s[0]);int m = Integer.parseInt(s[1]);int k = Integer.parseInt(s[2]);for(int i = 1; i <= m; i++){s = br.readLine().split(" ");int x = Integer.parseInt(s[0]);int y = Integer.parseInt(s[1]);int z = Integer.parseInt(s[2]);e[i] = new Node(x, y, z);}bellmanFord(n, m, k);}public static void bellmanFord(int n, int m, int k){Arrays.fill(d, INF);// 起点初始化为 0d[1] = 0;// 最多 k 条边,循环限制 k 次for(int i = 0; i < k; i++){// 拷贝数组,否则会有串联问题,导致计算边的数量不准确b = Arrays.copyOf(d, N);for(int j = 1; j <= m; j++){int x = e[j].x, y = e[j].y, z = e[j].z;d[y] = Math.min(d[y], b[x] + z);}}if(d[n] > INF / 2){System.out.println("impossible");}else{System.out.println(d[n]);}}static class Node{int x, y, z;public Node(int x, int y, int z){this.x = x;this.y = y;this.z = z;}}
}
相关文章:
52、有边数限制的最短路
有边数限制的最短路 题目描述 给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。 请你求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible。 注意:图中可…...
Spring boot实现基于注解的aop面向切面编程
Spring boot实现基于注解的aop面向切面编程 背景 从最开始使用Spring,AOP和IOC的理念就深入我心。正好,我需要写一个基于注解的AOP,被这个注解修饰的参数和属性,就会被拿到参数并校验参数。 一,引入依赖 当前sprin…...
MySQL之查询性能优化(四)
查询性能优化 MySQL客户端/服务器通信协议 一般来说,不需要去理解MySQL通信协议的内部实现细节,只需要大致理解通信协议是如何工作的。MySQL客户端和服务器之间的通信协议是"半双工"的,这意味着,在任何一个时刻&#…...
定时任务详解
文章目录 定时任务详解JDK自带第三方任务调度框架java有哪些定时任务的框架为什么需要定时任务定时任务扫表的方案有什么缺点Quartzxxl-jobxxl-job详解 elastic-job 定时任务详解 在定时任务中,操作系统或应用程序会利用计时器或定时器来定期检查当前时间是否达到了…...
OnlyOffice DocumentServer 8.0.1编译破解版本(¥100)
OnlyOffice DocumentServer 8.0.1编译破解版本(¥100) 破解20人数限制 更换中文字体 修改源码,根据业务自定义服务 根据源码在本机启动项目,便于开发 将编译好的服务打包docker镜像运行 提供各种docker镜像包&…...
Android 应用权限
文章目录 权限声明uses-permissionpermissionpermission-grouppermission-tree其他uses-feature 权限配置 权限声明 Android权限在AndroidManifest.xml中声明,<permission>、 <permission-group> 、<permission-tree> 和<uses-permission>…...
MATLAB 匿名函数
定义匿名函数定义匿名函数的基本语法如下:示例示例 1:简单数学运算示例 2:字符串操作示例 3:作为参数传递 匿名函数的高级用法使用函数句柄定义多输出函数使用局部变量使用嵌套匿名函数 注意事项 匿名函数( Anonymous…...
Java 新手入门:基础知识点一览
Java 新手入门:基础知识点一览 想要踏入 Java 的编程世界?别担心,这篇文章将用简单易懂的表格形式,带你快速了解 Java 的基础知识点。 一、Java 是什么? 概念解释Java一种面向对象的编程语言,拥有跨平台、…...
三维模型轻量化工具:手工模型、BIM、倾斜摄影等皆可用!
老子云是全球领先的数字孪生引擎技术及服务提供商,它专注于让一切3D模型在全网多端轻量化处理与展示,为行业数字化转型升级与数字孪生应用提供成套的3D可视化技术、产品与服务。 老子云是全球领先的数字孪生引擎技术及服务提供商,它专注于让…...
小程序CI/CD之自动化打包预览并钉钉通知发布进程
小程序打包方式分为两种:手动打包、自动打包 那如何实现 自动打包 呐?我们今天就来聊一聊! 首先,很重要,看 官方文档 这里提到今天我们要聊的“主角” miniprogram-ci miniprogram-ci 是从微信开发者工具中抽离的关于…...
C++使用QtHttpServer开发服务端Server的Http POST接口和客户端Client示例
Client HTTP POST 假设http://127.0.0.1:8888/post/是一个能够接受POST请求的路径,我们想要向它提交一段json数据,用Qt可以这样实现: Suppose we want to make an HTTP POST with json body to http://127.0.0.1:8888/post/. QCoreApplica…...
计算机基础(8)——音频数字化(模电与数电)
💗计算机基础系列文章💗 👉🍀计算机基础(1)——计算机的发展史🍀👉🍀计算机基础(2)——冯诺依曼体系结构🍀👉ἴ…...
手搓单链表(无哨兵位)(C语言)
目录 SLT.h SLT.c SLTtest.c 测试示例 单链表优劣分析 SLT.h #pragma once#include <stdio.h> #include <assert.h> #include <stdlib.h>typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next; }SLTNode;//打印…...
代码随想录算法训练营第18天|二叉树
513. 找树左下角的值 最左边的结点的特性 1.只能是叶子结点, 2.必须考虑是最底层,所以要考虑树的深度 3.同样的深度考虑左子树 考虑迭代法,层序遍历 递归优点难搞的 /*** Definition for a binary tree node.* function TreeNode(val, left, righ…...
使用tftpd更新开发板内核
我们升级内核可以通过原厂提供的升级软件来进行,比如瑞芯微的RKDevTool.exe,只不过这种方式必须通过指定的OTG升级口,还得借助按键进入loader模式后才可以。 其实还可以利用一些通用的工具来进行升级,比如tftpd工具。 下载地址p…...
MySQL数据库整体知识点简述
目录 第一章:数据库系统概述 第二章:信息与数据模型 第3章 关系模型与关系规范化理论 第四章——数据库设计方法 第六-七章——MySQL存储引擎与数据库操作管理 第九章——索引 第10章——视图 第11章——MySQL存储过程与函数 第12章——MySQL 触…...
深入理解MySQL索引下推优化
在MySQL中,索引的使用对于查询性能至关重要。然而,即使有合适的索引,有时查询性能仍然不尽如人意。索引下推(Index Condition Pushdown,ICP)是一项能够进一步优化查询性能的技术。本文将详细讲解索引下推的…...
论文降重技巧:AI工具如何助力论文原创性提升?
论文降重一直是困扰各界毕业生的“拦路虎”,还不容易熬过修改的苦,又要迎来降重的痛。 其实想要给论文降重达标,我有一些独家秘诀。话不多说直接上干货! 1、同义词改写(针对整段整句重复) 这是最靠谱也是…...
el-date-picker的使用,及解决切换type时面板样式错乱问题
这里选择器的类型可以选择日月年和时间范围,根据类型不同,el-date-picker的面板也展示不同,但是会出现el-date-picker错位,或者面板位置和层级等问题。 源代码: <el-selectv-model"dateType"placeholder&…...
Flutter 中的 ToggleButtonsTheme 小部件:全面指南
Flutter 中的 ToggleButtonsTheme 小部件:全面指南 Flutter,作为由 Google 开发的跨平台 UI 框架,为开发者提供了丰富的组件来构建现代化的应用程序。ToggleButtons 是 Material Design 组件库中的一个组件,它允许用户从一组选项…...
洗衣留香珠市场:其中亚太地区以12.5%的增速领跑全球市场
据权威市场研究机构预测,2024年全球洗衣留香珠市场规模预计突破35亿美元,年复合增长率达8.2%,其中亚太地区以12.5%的增速领跑全球市场。这一功能性香氛产品正从附加型消费向日常洗护必需品转型,其技术迭代与市场渗透呈现出高端化、…...
数学动画音频同步:让几何图形随音乐起舞的技术实现
数学动画音频同步:让几何图形随音乐起舞的技术实现 【免费下载链接】manim A community-maintained Python framework for creating mathematical animations. 项目地址: https://gitcode.com/GitHub_Trending/man/manim 在数学可视化领域,Manim…...
IntelliJ IDEA中SVN与Git版本管理的高效配置指南
1. 为什么需要版本管理工具? 如果你曾经因为误删代码而熬夜重写,或者因为团队协作时文件覆盖而崩溃,那你一定需要版本管理工具。想象一下,代码就像写作文时的草稿纸——每次修改都保留历史版本,随时可以回退到上周二下…...
网络调试无从下手?Fiddler中文版让HTTP问题排查效率提升10倍的秘密
网络调试无从下手?Fiddler中文版让HTTP问题排查效率提升10倍的秘密 【免费下载链接】zh-fiddler Fiddler Web Debugger 中文版 项目地址: https://gitcode.com/gh_mirrors/zh/zh-fiddler 在当今复杂的网络环境中,开发者和测试工程师经常面临HTTP请…...
为什么数据质量成为人工智能领域最重要的问题
简而言之:传统的基于人工编写规则和被动检查的数据质量体系,从未针对智能体人工智能进行设计。到2026年,当自主代理处理错误数据时,没有人会介入以发现问题。那些在人工智能领域取得成功的组织,并非从更好的模型入手&a…...
万象视界灵坛代码实例:使用Gradio快速搭建像素风Web UI,零前端开发经验可用
万象视界灵坛代码实例:使用Gradio快速搭建像素风Web UI,零前端开发经验可用 1. 项目概述 万象视界灵坛是一款基于OpenAI CLIP模型的多模态智能感知平台,它将复杂的语义对齐功能包装在充满游戏感的像素风界面中。这个项目最大的特点是完全不…...
3步解决字幕处理90%的麻烦:BiliBiliCCSubtitle效率革命
3步解决字幕处理90%的麻烦:BiliBiliCCSubtitle效率革命 【免费下载链接】BiliBiliCCSubtitle 一个用于下载B站(哔哩哔哩)CC字幕及转换的工具; 项目地址: https://gitcode.com/gh_mirrors/bi/BiliBiliCCSubtitle 开篇:三个真实场景的效率反差 场景…...
PaddleNLP:面向产业级应用的大语言模型全流程开发套件技术深度解析
PaddleNLP:面向产业级应用的大语言模型全流程开发套件技术深度解析 【免费下载链接】PaddleNLP PaddleNLP是一款基于飞桨深度学习框架的大语言模型(LLM)开发套件,支持在多种硬件上进行高效的大模型训练、无损压缩以及高性能推理。PaddleNLP 具备简单易用…...
17种智能体(Agent)架构全景解析:演进逻辑、工程价值与落地实践
17种智能体(Agent)架构按“单体→增强→工具→多智能体→操作系统级”的演进路径,分为5大类,核心逻辑是从简单到复杂、从基础到前沿,兼顾工程落地性和理论完整性。以下将对每一种架构模式进行详细拆解,结合…...
Pixel Aurora Engine 辅助UI/UX设计:自动生成界面原型与素材
Pixel Aurora Engine 辅助UI/UX设计:自动生成界面原型与素材 1. 设计效率的革命性提升 想象一下这样的场景:产品经理刚描述完"我们需要一个社交App的登录页,要简洁现代感,带点科技风",几分钟后,…...
