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

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 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开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的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; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...