当前位置: 首页 > 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 后进行串联, 并将其中一台作为主服务器暴露给内网…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

【JavaWeb】Docker项目部署

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

vue3+vite项目中使用.env文件环境变量方法

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

以光量子为例,详解量子获取方式

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

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势

一、WebRTC与智能硬件整合趋势​ 随着物联网和实时通信需求的爆发式增长&#xff0c;WebRTC作为开源实时通信技术&#xff0c;为浏览器与移动应用提供免插件的音视频通信能力&#xff0c;在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能&#xff0c;对实时…...

统计学(第8版)——统计抽样学习笔记(考试用)

一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征&#xff08;均值、比率、总量&#xff09;控制抽样误差与非抽样误差 解决的核心问题 在成本约束下&#xff0c;用少量样本准确推断总体特征量化估计结果的可靠性&#xff08;置…...