acwing算法基础之搜索与图论--floyd算法
目录
- 1 基础知识
- 2 模板
- 3 工程化
1 基础知识
floyd算法的时间复杂度为O(n^3),它用来解决多源最短路问题。它的原理是基于动态规划。
floyd算法的关键步骤:
- k从1到n。
- i从1到n。
- j从1到n,d[i][j] = min(d[i][j], d[i][k] + d[k][j])。
- 经过上述三重循环之后,数组d即是任意两个结点之间的最短距离。
2 模板
初始化: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;// 算法结束后,d[a][b]表示a到b的最短距离
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]);
}
3 工程化
题目1:求两两结点之间的最短距离。
#include <iostream>using namespace std;const int N = 210;
int n, m, q;
int d[N][N];int main() {cin >> 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] = 0x3f3f3f3f;}}int a, b, c;while (m--) {cin >> a >> b >> c;d[a][b] = min(d[a][b], c);}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]);}}}while (q--) {cin >> a >> b;if (d[a][b] > 0x3f3f3f3f / 2) cout << "impossible" << endl;else cout << d[a][b] << endl;}return 0;
}
相关文章:
acwing算法基础之搜索与图论--floyd算法
目录 1 基础知识2 模板3 工程化 1 基础知识 floyd算法的时间复杂度为O(n^3),它用来解决多源最短路问题。它的原理是基于动态规划。 floyd算法的关键步骤: k从1到n。i从1到n。j从1到n,d[i][j] min(d[i][j], d[i][k] d[k][j])。经过上述三…...
Zabbix监控SSL证书有效期
一、介绍 由于业务需要,最近通过 Let’s Encrypt 申请了一些 SSL 证书,而证书有效期为 3 个月,需要在证书到期之前 renew。由于域名较多经常忘记 renew,导致证书过期,因此想通过 Zabbix 的方式监控证书的到期时间&…...
Arduino OneButton按键处理库实现单击/双击/长按功能
Arduino OneButton按键处理库实现单击/双击长按功能 ✨在Arduino开发平台下,按键的单击/双击/长按功能,在通过使用OneButton库,很容易就可以轻松实现。这就是支持C/C模块化设计的好处,避免重复性开发的工作。 🔖本文将…...
day52 django的下载与安装
课程的大致安排 大概两周的时间都是围绕着Django框架的学习,包括后续要学习的drf、Redis、celery、es等技术栈都是围绕Django展开的,因此、要求所有的同学必须认证学习了 市场中所有使用Python开发的web项目,Django框架占有率达到90%以上 …...
WebGL智慧城市软件项目
WebGL开发智慧城市项目时,需要考虑多个方面,包括技术、隐私、安全和可持续性。以下是一些需要注意的关键问题,希望对大家有所帮助。北京木奇移动技术有限公司,专业的软件外包开发公司,欢迎交流合作。 1.隐私和数据安全…...
VMware重装后没有虚拟网卡
我重装VMware之后网络适配器里面没有虚拟网卡,找了CSDN上很多博主说的,都没用。 最终去看了b站的up视频就成功了。 原因是因为第一次安装后卸载不干净,软件在电脑上的注册表没有删掉。 要用下面两个软件清理一下残留文件,这两个…...
软件安全基础
传参基础 64位汇编传参,当参数少于7个时, 参数从左到右放入寄存器: rdi, rsi, rdx, rcx, r8, r9。 当参数为7个以上时, 前 6 个与前面一样, 但后面的依次从 “右向左” 放入栈中,即和32位汇编一样。 我们这边要利用wr…...
探索项目管理软件的多重用途和益处
项目管理软件俨然成了当下项目管理话题中的热门词条,作为一个辅助性管理工具,项目管理软件有什么用?真的值得购入吗? 什么是项目管理软件 顾名思义,项目管理软件就是指在项目管理过程使用的各种软件工具。项目管理软件…...
Arduino ESP8266使用AliyunIoTSDK.h连接阿里云物联网平台
文章目录 1、AliyunIoTSDK简介2、相关库安装3、阿里云创建产品,订阅发布4、对开源的Arduino ESP8266源代码修改5、使用阿里云点亮一个LED灯6、设备向阿里云上传温度数据7、项目源码 1、AliyunIoTSDK简介 AliyunIoTSDK是arduino的一个库,可以在arduino的…...
【车载开发系列】AutoSar中的CANTP
【车载开发系列】AutoSar中的CANTP 【车载开发系列】AutoSar中的CANTP 【车载开发系列】AutoSar中的CANTP一. CANTP相关术语二. CANTP相关概念1)单帧:SF(Single Frame)2)首帧:FF(First Frame)3)连续帧CF(Consecutive F…...
JUL日志
文章目录 JUL日志JUL日志讲解Properties配置文件编写日志配置文件Lombok快速开启日志Mybatis日志系统 JUL日志 如果使用System.out.println来打印信息,项目中存在大量的控制台输出语句,会显得很凌乱,而且日志的粒度是不够细的,假…...
ZZ308 物联网应用与服务赛题第G套
2023年全国职业院校技能大赛 中职组 物联网应用与服务 任 务 书 (G卷) 赛位号:______________ 竞赛须知 一、注意事项 1.检查硬件设备、电脑设备是否正常。检查竞赛所需的各项设备、软件和竞赛材料等; 2.竞赛任务中所使用…...
如何使用 vcpkg 编译Google-V8脚本引擎(ECMA/JavaScript)?
WIN32K下一键杀死所有同名进程命令行:taskkill /F /IM chrome.exe ############################## 1、准备 Visual Studio 2019 2、准备 Visual Studio 2022 3、安装 VC、MSBuild 编译集成环境 4、安装 Python 3.x,早期V8发行版本编译安装 2.x 5、…...
系列二十二、idea Live Templates
一、idea Live Templates 1.1、Java Group 1.1.1、fast fast 快速在类上添加注解Data AllArgsConstructor NoArgsConstructor Accessors(chain true) ToString(callSuper true) 1.1.2、getThreadName getThreadName快速获取当前线程的名字Thread.currentThread().getName…...
电脑本地安装宝塔/docker 安装宝塔
一、先去docker官网(http://docker.com)下载软件并进行安装,网站打不开多试几次或者找梯子。 二、macos系统里按“command 空格”搜索“终端”回车,启动终端程序。 三、执行下面命令,拉取docker镜像。 docker pull pch18/baota:clear pch…...
Java Lambda 表达式笔记
文章目录 Java Lambda 表达式语法Lambda 表达式实例Lambda表达式与函数式接口方法引用处理lambda表达式的接口 Java Lambda 表达式语法Lambda 表达式实例Lambda表达式与函数式接口方法引用处理lambda表达式的接口 Java Lambda 表达式 Lambda 表达式,也可称为闭包. …...
Flutter笔记:状态提升、控制器模式、GetX控制器和服务
Flutter笔记 状态提升、控制器模式、GetX控制器和服务 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263/article/details/1…...
9.spark自适应查询-AQE之动态调整Join策略
目录 概述动态调整Join策略原理实战 动态优化倾斜的 Join原理实战 概述 broadcast hash join 类似于 Spark 共享变量中的广播变量,Spark join 如果能采取这种策略,那join 的性能是最好的 自适应查询AQE(Adaptive Query Execution) 动态调整Join策略 原…...
CentOs7 NAT模式连接网络
1.配置动态网络 1.1 检查主机网卡配置 检查主机的网络设置 进入控制面板,找到网络共享中心 查看适配器是否都已经开启 1.2 设置虚拟机的网络配置 打开虚拟机网络配置设置,对网卡VMnet8 进行设置 记住网关 全部选择应用,确定 1.3 设置…...
linux安装git
目录 声明 前言 正文 (1)下载git压缩包 (2)git压缩包解压 (3)解压完成后需要进行源码的编译操作 a.首先进去到解压后的文件目录中: b.执行: 编译的过程中可能遇到的问题&am…...
从零组装一台能联网的电脑:手把手记录我的南邮电装实习全过程(含BIOS设置与网络配置)
从零组装一台能联网的电脑:手把手记录我的南邮电装实习全过程 第一次亲手组装电脑的体验,远比想象中更令人兴奋。作为电子信息工程专业的学生,这次电装实习让我从理论走向实践,完整经历了从零配件到联网主机的全过程。如果你也和我…...
Claude Code Auto Mode 的技术实现
Claude Code Auto Mode 通过智能代码补全和上下文理解提升编程效率。该模式能自动分析当前代码上下文,预测开发者意图,提供精准的代码建议。支持多种编程语言,包括Python、JavaScript、Java等主流语言。深度学习模型实时学习项目代码风格和模…...
ChibiPIO-STM32F0:专为Cortex-M0优化的ChibiOS定制发行版
1. 项目概述ChibiPIO-STM32F0 是一个面向 STM32F0 系列微控制器的定制化 ChibiOS/RT 嵌入式实时操作系统发行版,其核心定位并非独立开发的新RTOS,而是对上游 ChibiOS/RT 源码树进行深度裁剪、适配与封装后的专用构建产物。它完整继承 ChibiOS/RT 的轻量级…...
G-Helper技术深度解析:华硕硬件控制架构揭秘与性能优化实践
G-Helper技术深度解析:华硕硬件控制架构揭秘与性能优化实践 【免费下载链接】g-helper Lightweight, open-source control tool for ASUS laptops and ROG Ally. Manage performance modes, fans, GPU, battery, and RGB lighting across Zephyrus, Flow, TUF, Stri…...
RK3588嵌入式Linux开发实战:uboot镜像合成与rkbin文件整合指南
1. RK3588开发必备:理解uboot镜像合成的核心意义 刚接触RK3588开发板时,很多工程师都会困惑:为什么编译好的uboot不能直接烧录?这个问题我最初也踩过坑。实际上,Rockchip平台的启动流程比传统嵌入式系统更复杂…...
Three.js 3D热力图实现全解析(从原理到实战)
1. 3D热力图的核心原理与实现思路 第一次接触3D热力图时,我也被那些酷炫的立体数据可视化效果惊艳到了。这种技术本质上是通过颜色和高度两个维度来呈现数据密度分布,比传统的2D热力图多了Z轴信息。在Three.js中实现这个效果,关键要理解三个核…...
EspMQTTClient:ESP32/ESP8266的Wi-Fi+MQTT一体化连接框架
1. EspMQTTClient 库深度解析:面向嵌入式工程师的 Wi-Fi 与 MQTT 一体化连接方案EspMQTTClient 是专为 ESP8266 和 ESP32 平台设计的轻量级、高鲁棒性网络通信库,其核心目标并非简单封装底层 SDK API,而是构建一套面向生产环境的连接生命周期…...
5分钟上手IndexTTS2:让AI语音合成真正听懂你的情感!
5分钟上手IndexTTS2:让AI语音合成真正听懂你的情感! 【免费下载链接】index-tts An Industrial-Level Controllable and Efficient Zero-Shot Text-To-Speech System 项目地址: https://gitcode.com/gh_mirrors/in/index-tts 还在为视频配音找不到…...
【Python】CairoSVG实战:从SVG到多格式转换的完整指南
1. 为什么选择CairoSVG进行SVG转换 如果你经常需要处理矢量图形,肯定遇到过这样的场景:设计部门给你发来SVG文件,但你的应用场景需要PNG格式;或者需要把SVG图标批量导出为PDF文档。这时候CairoSVG就是你的瑞士军刀。 我在实际项目…...
从领域驱动到本体论:AI 时代的架构方法论变了对
从0构建WAV文件:读懂计算机文件的本质 虽然接触计算机有一段时间了,但是我的视野一直局限于一个较小的范围之内,往往只能看到于算法竞赛相关的内容,计算机各种文件在我看来十分复杂,认为构建他们并能达到目的是一件困难…...
