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

Floyd(弗洛伊德)算法总结

知识概览

  • Floyd算法适合解决多源汇最短路问题,其中源点是起点,汇点是终点。时间复杂度是O(n^3)

例题展示

题目链接

活动 - AcWing 系统讲解常用算法与数据结构,给出相应代码模板,并会布置、讲解相应的基础算法题目。icon-default.png?t=N7T8https://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;
}

参考资料

  1. AcWing算法基础课

相关文章:

Floyd(弗洛伊德)算法总结

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

西南科技大学计算机网络实验二 (IP协议分析与以太网协议分析)

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

SICP : The Elements of Programming

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

支付宝、学习强国小程序input、textarea数据双向绑定

前言 和 vue 的绑定有些区别&#xff0c;需要注意。直接 value"{{inputValue}}" 是无法双向绑定的。 正确思路 文档说的比较详细&#xff0c;不过没有组合使用的案例&#xff0c;需要自行理解。这里正确的方法是先用 value 绑定数据&#xff0c;再使用 onInput 事件…...

AI“百模大战”现状:向垂直、B端谋场景,算力仍是主要制约因素

文章目录 每日一句正能量前言AI&#xff08;人工智能&#xff09;大模型正“飞入”百姓家和行业中。向垂直、B端谋场景算力仍是主要制约因素构建“数据-模型-应用”飞轮后记 每日一句正能量 我们必须在失败中寻找胜利&#xff0c;在绝望中寻求希望。 前言 在当前快速发展的人工…...

手机上的软件怎么修改网络IP地址

在手机上修改网络IP地址通常需要通过以下两种方法&#xff1a; 1. 使用VPN&#xff08;虚拟私人网络&#xff09;或代理软件&#xff1a; 步骤如下&#xff1a; - 下载并安装一个可靠的VPN或代理软件到你的手机上。 - 打开VPN或代理软件&#xff0c;选择一个你希望获取IP地址…...

返回按钮点击坐标

返回按钮的点击坐标&#xff08;按钮本身的相对位置&#xff09;主要用于自绘控件时响应点击对应的数据变化。效果如下图&#xff1a; 代码实现 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 寄存器&#xff0c;不像x86用户态可以直接读取&#xff0c;需内核态使能&#xff0c;一种是在内核中使能&#xff0c;比如init&#xff0c;比较简单的是在模块中使能。 本来写了两个&#xff0c;arm32一个&#xff0c;arm64一个&#xff0c;方…...

vue 项目/备案网页/ip网页打包成 apk 安装到平板/手机(含vue项目跨域代理打包成apk后无法访问接口的解决方案)

下载安装HBuilder X编辑器 https://www.dcloud.io/hbuilderx.html 新建 5APP 项目 打开 HBuilder X&#xff0c;新建项目 此处项目名以 ‘test’ 为例 含跨域代理的vue项目改造 若 vue 项目中含跨域代理&#xff0c;如 vue.config.js module.exports {publicPath: "./&…...

面试复盘4——后端开发——一面

前言 本文主要用于个人复盘学习&#xff0c;因此为保障公平&#xff0c;所以本文不指出公司名&#xff0c;题目编号只是为了自己区别而已。对待面经&#xff0c;望读者还是更多从其中学习总结&#xff0c;而不是去碰原题。 面试岗位信息 北京某初创&#xff0c;go开发&#…...

使用 Postman 进行并发请求:实用教程与最佳实践

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

河南工程学院第六届程序设计竞赛-A组-题解

更好的阅读体验 \color{red}{更好的阅读体验} 更好的阅读体验 远古时期的签到题 原题链接 描述&#xff1a; 远古时期奇妙的事情… 远古时期有一个比赛&#xff0c;里面有这样一道签到题&#xff1a; 给定一个正整数 N N N求这个整数转化为二进制后的数有多少位是 0 0 0。…...

韩版传奇 2 源码分析与 Unity 重制(二)客户端启动与交互流程

专题介绍 该专题将会分析 LOMCN 基于韩版传奇 2&#xff0c;使用 .NET 重写的传奇源码&#xff08;服务端 客户端&#xff09;&#xff0c;分析数据交互、状态管理和客户端渲染等技术&#xff0c;此外笔者还会分享将客户端部分移植到 Unity 和服务端用现代编程语言重写的全过…...

JVM面试——运行时数据区

一&#xff1a;JVM的运行时内存区域是怎样的? 根据Java虚拟机规范的定义&#xff0c;JVM的运行时内存区域主要由程序计数器、虚拟机栈、本地方法 栈、Java堆、方法区和以及运行时常量池组成。其中堆、方法区以及运行时常量池是线程之间共享的区域&#xff0c;而栈&#xff08…...

ssh工具 向指定的ssh服务器配置公钥

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

uni-app pages.json之globalStyle全局页面样式配置

锋哥原创的uni-app视频教程&#xff1a; 2023版uniapp从入门到上天视频教程(Java后端无废话版)&#xff0c;火爆更新中..._哔哩哔哩_bilibili2023版uniapp从入门到上天视频教程(Java后端无废话版)&#xff0c;火爆更新中...共计23条视频&#xff0c;包括&#xff1a;第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消息队列运行环境

这篇文章&#xff0c;主要介绍如何安装RocketMQ消息队列运行环境。 目录 一、RocketMQ消息队列 1.1、下载RocketMQ 1.2、解压安装包 1.3、配置RocketMQ环境变量 1.4、修改启动脚本 1.5、启动RocketMQ &#xff08;1&#xff09;启动NameServer &#xff08;2&#xff0…...

使用 Privoxy 实现对多域名的定向转发

需求与思路 内网一台主机想要访问公网的两个不同站点, 想要实现访问两个站点时表现出不同的公网 IP 地址. 即在公网的站点服务器端看到的客户端 IP 是不同的. 思路是搭建两台具有不同公网 IP 的服务器, 分别安装配置 Privoxy 后进行串联, 并将其中一台作为主服务器暴露给内网…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...