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

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...