Floyd(弗洛伊德)算法总结
知识概览
- Floyd算法适合解决多源汇最短路问题,其中源点是起点,汇点是终点。时间复杂度是
。
例题展示
题目链接
活动 - AcWing 系统讲解常用算法与数据结构,给出相应代码模板,并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/856/
题解
Floyd算法基于动态规划的思想,主要是三重循环,先遍历k,i和j的遍历顺序谁先谁后都可以。
代码
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 210, INF = 1e9;int n, m, Q;
int d[N][N];void floyd()
{for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}int main()
{scanf("%d%d%d", &n, &m, &Q);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (i == j) d[i][j] = 0;else d[i][j] = INF;while (m--){int a, b, w;scanf("%d%d%d", &a, &b, &w);d[a][b] = min(d[a][b], w);}floyd();while (Q--){int a, b;scanf("%d%d", &a, &b);if (d[a][b] > INF / 2) puts("impossible");else printf("%d\n", d[a][b]);}return 0;
}
参考资料
- AcWing算法基础课
相关文章:

Floyd(弗洛伊德)算法总结
知识概览 Floyd算法适合解决多源汇最短路问题,其中源点是起点,汇点是终点。时间复杂度是。 例题展示 题目链接 活动 - AcWing 系统讲解常用算法与数据结构,给出相应代码模板,并会布置、讲解相应的基础算法题目。https://www.acw…...

西南科技大学计算机网络实验二 (IP协议分析与以太网协议分析)
一、实验目的 通过分析由跟踪执行traceroute程序发送和接收捕获得到的IP 数据报,深入研究在IP 数据报中的各种字段,理解IP协议。基于ARP命令和Ethereal进行以太网帧捕获与分析,理解和熟悉ARP协议原理以及以太网帧格式。 二、实验环境 与因特网连接的计算机网络系统;主机操…...

SICP : The Elements of Programming
好的计算机编程语言应具备的三个特性 基础单元表达式,计算机编程语言最最最基础单元,理应具备的表达式组合的能力,能够通过基础单元表达式组合成更复杂的元素抽象的能力,能通过复杂的元素抽象成更高层的单元 基础单元表达式 加 …...

支付宝、学习强国小程序input、textarea数据双向绑定
前言 和 vue 的绑定有些区别,需要注意。直接 value"{{inputValue}}" 是无法双向绑定的。 正确思路 文档说的比较详细,不过没有组合使用的案例,需要自行理解。这里正确的方法是先用 value 绑定数据,再使用 onInput 事件…...

AI“百模大战”现状:向垂直、B端谋场景,算力仍是主要制约因素
文章目录 每日一句正能量前言AI(人工智能)大模型正“飞入”百姓家和行业中。向垂直、B端谋场景算力仍是主要制约因素构建“数据-模型-应用”飞轮后记 每日一句正能量 我们必须在失败中寻找胜利,在绝望中寻求希望。 前言 在当前快速发展的人工…...
手机上的软件怎么修改网络IP地址
在手机上修改网络IP地址通常需要通过以下两种方法: 1. 使用VPN(虚拟私人网络)或代理软件: 步骤如下: - 下载并安装一个可靠的VPN或代理软件到你的手机上。 - 打开VPN或代理软件,选择一个你希望获取IP地址…...

返回按钮点击坐标
返回按钮的点击坐标(按钮本身的相对位置)主要用于自绘控件时响应点击对应的数据变化。效果如下图: 代码实现 private void button1_MouseClick(object sender, MouseEventArgs e){Point p e.Location;this.Text p.ToString();} 利用 Mouse…...
arm32 arm64 读取PMCCNTR cpu cycle counter
ARM 的时钟周期计数保存在PMCCNTR 寄存器,不像x86用户态可以直接读取,需内核态使能,一种是在内核中使能,比如init,比较简单的是在模块中使能。 本来写了两个,arm32一个,arm64一个,方…...

vue 项目/备案网页/ip网页打包成 apk 安装到平板/手机(含vue项目跨域代理打包成apk后无法访问接口的解决方案)
下载安装HBuilder X编辑器 https://www.dcloud.io/hbuilderx.html 新建 5APP 项目 打开 HBuilder X,新建项目 此处项目名以 ‘test’ 为例 含跨域代理的vue项目改造 若 vue 项目中含跨域代理,如 vue.config.js module.exports {publicPath: "./&…...
面试复盘4——后端开发——一面
前言 本文主要用于个人复盘学习,因此为保障公平,所以本文不指出公司名,题目编号只是为了自己区别而已。对待面经,望读者还是更多从其中学习总结,而不是去碰原题。 面试岗位信息 北京某初创,go开发&#…...

使用 Postman 进行并发请求:实用教程与最佳实践
背景介绍 最近,我们发起了一个在线图书管理系统的项目。我负责的一个关键模块包括三个主要后台接口: 实现对books数据的检索。实施对likes数据的获取。通过collections端点访问数据。 应对高流量的挑战 在设计并部署接口时,我们不可避免地…...

河南工程学院第六届程序设计竞赛-A组-题解
更好的阅读体验 \color{red}{更好的阅读体验} 更好的阅读体验 远古时期的签到题 原题链接 描述: 远古时期奇妙的事情… 远古时期有一个比赛,里面有这样一道签到题: 给定一个正整数 N N N求这个整数转化为二进制后的数有多少位是 0 0 0。…...
韩版传奇 2 源码分析与 Unity 重制(二)客户端启动与交互流程
专题介绍 该专题将会分析 LOMCN 基于韩版传奇 2,使用 .NET 重写的传奇源码(服务端 客户端),分析数据交互、状态管理和客户端渲染等技术,此外笔者还会分享将客户端部分移植到 Unity 和服务端用现代编程语言重写的全过…...
JVM面试——运行时数据区
一:JVM的运行时内存区域是怎样的? 根据Java虚拟机规范的定义,JVM的运行时内存区域主要由程序计数器、虚拟机栈、本地方法 栈、Java堆、方法区和以及运行时常量池组成。其中堆、方法区以及运行时常量池是线程之间共享的区域,而栈(…...

ssh工具 向指定的ssh服务器配置公钥
此文分享一个python脚本,用于向指定的ssh服务器配置公钥,以达到免密登录ssh服务器的目的。 效果演示 🔥完整演示效果 👇第一步,显然,我们需要选择功能 👇第二步,确认 or 选择ssh服务器 👇第三步,输入ssh登录密码,以完成公钥配置 👇验证,我们通过ssh登录…...

uni-app pages.json之globalStyle全局页面样式配置
锋哥原创的uni-app视频教程: 2023版uniapp从入门到上天视频教程(Java后端无废话版),火爆更新中..._哔哩哔哩_bilibili2023版uniapp从入门到上天视频教程(Java后端无废话版),火爆更新中...共计23条视频,包括:第1讲 uni…...

Blazor 混合开发_MAUI+Vue_WPF+Vue
Blazor 混合开发_MAUIVue_WPFVue 背景混合开发的核心为什么必须使用 wwwroot 文件夹放置 Web 项目文件 创建 MAUI 项目创建 wwwroot 文件夹服务注册创建 _import.razor添加 Main.razor 组件修改 MainPage.xaml 文件 创建 WPF 项目创建 wwwroot 文件夹服务注册创建 _import.razo…...
udp异步方式接收消息
C#实现 //定义结构体 public struct UdpState { public UdpClient u; public IPEndPoint e; } private UdpClient _client; //_client的初始化请参考其他资料 IPEndPoint remoteEP null; //TODO //public static bool mess…...

【RocketMQ笔记01】安装RocketMQ消息队列运行环境
这篇文章,主要介绍如何安装RocketMQ消息队列运行环境。 目录 一、RocketMQ消息队列 1.1、下载RocketMQ 1.2、解压安装包 1.3、配置RocketMQ环境变量 1.4、修改启动脚本 1.5、启动RocketMQ (1)启动NameServer (2࿰…...
使用 Privoxy 实现对多域名的定向转发
需求与思路 内网一台主机想要访问公网的两个不同站点, 想要实现访问两个站点时表现出不同的公网 IP 地址. 即在公网的站点服务器端看到的客户端 IP 是不同的. 思路是搭建两台具有不同公网 IP 的服务器, 分别安装配置 Privoxy 后进行串联, 并将其中一台作为主服务器暴露给内网…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...

vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...

EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势
一、WebRTC与智能硬件整合趋势 随着物联网和实时通信需求的爆发式增长,WebRTC作为开源实时通信技术,为浏览器与移动应用提供免插件的音视频通信能力,在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能,对实时…...
统计学(第8版)——统计抽样学习笔记(考试用)
一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征(均值、比率、总量)控制抽样误差与非抽样误差 解决的核心问题 在成本约束下,用少量样本准确推断总体特征量化估计结果的可靠性(置…...