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

acwing算法基础之搜索与图论--floyd算法

目录

  • 1 基础知识
  • 2 模板
  • 3 工程化

1 基础知识

floyd算法的时间复杂度为O(n^3),它用来解决多源最短路问题。它的原理是基于动态规划。

floyd算法的关键步骤:

  1. k从1到n。
  2. i从1到n。
  3. j从1到n,d[i][j] = min(d[i][j], d[i][k] + d[k][j])。
  4. 经过上述三重循环之后,数组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)&#xff0c;它用来解决多源最短路问题。它的原理是基于动态规划。 floyd算法的关键步骤&#xff1a; k从1到n。i从1到n。j从1到n&#xff0c;d[i][j] min(d[i][j], d[i][k] d[k][j])。经过上述三…...

Zabbix监控SSL证书有效期

一、介绍 由于业务需要&#xff0c;最近通过 Let’s Encrypt 申请了一些 SSL 证书&#xff0c;而证书有效期为 3 个月&#xff0c;需要在证书到期之前 renew。由于域名较多经常忘记 renew&#xff0c;导致证书过期&#xff0c;因此想通过 Zabbix 的方式监控证书的到期时间&…...

Arduino OneButton按键处理库实现单击/双击/长按功能

Arduino OneButton按键处理库实现单击/双击长按功能 ✨在Arduino开发平台下&#xff0c;按键的单击/双击/长按功能&#xff0c;在通过使用OneButton库&#xff0c;很容易就可以轻松实现。这就是支持C/C模块化设计的好处&#xff0c;避免重复性开发的工作。 &#x1f516;本文将…...

day52 django的下载与安装

课程的大致安排 大概两周的时间都是围绕着Django框架的学习&#xff0c;包括后续要学习的drf、Redis、celery、es等技术栈都是围绕Django展开的&#xff0c;因此、要求所有的同学必须认证学习了 市场中所有使用Python开发的web项目&#xff0c;Django框架占有率达到90%以上 …...

WebGL智慧城市软件项目

WebGL开发智慧城市项目时&#xff0c;需要考虑多个方面&#xff0c;包括技术、隐私、安全和可持续性。以下是一些需要注意的关键问题&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 1.隐私和数据安全…...

VMware重装后没有虚拟网卡

我重装VMware之后网络适配器里面没有虚拟网卡&#xff0c;找了CSDN上很多博主说的&#xff0c;都没用。 最终去看了b站的up视频就成功了。 原因是因为第一次安装后卸载不干净&#xff0c;软件在电脑上的注册表没有删掉。 要用下面两个软件清理一下残留文件&#xff0c;这两个…...

软件安全基础

传参基础 64位汇编传参&#xff0c;当参数少于7个时&#xff0c; 参数从左到右放入寄存器: rdi, rsi, rdx, rcx, r8, r9。 当参数为7个以上时&#xff0c; 前 6 个与前面一样&#xff0c; 但后面的依次从 “右向左” 放入栈中&#xff0c;即和32位汇编一样。 我们这边要利用wr…...

探索项目管理软件的多重用途和益处

项目管理软件俨然成了当下项目管理话题中的热门词条&#xff0c;作为一个辅助性管理工具&#xff0c;项目管理软件有什么用&#xff1f;真的值得购入吗&#xff1f; 什么是项目管理软件 顾名思义&#xff0c;项目管理软件就是指在项目管理过程使用的各种软件工具。项目管理软件…...

Arduino ESP8266使用AliyunIoTSDK.h连接阿里云物联网平台

文章目录 1、AliyunIoTSDK简介2、相关库安装3、阿里云创建产品&#xff0c;订阅发布4、对开源的Arduino ESP8266源代码修改5、使用阿里云点亮一个LED灯6、设备向阿里云上传温度数据7、项目源码 1、AliyunIoTSDK简介 AliyunIoTSDK是arduino的一个库&#xff0c;可以在arduino的…...

【车载开发系列】AutoSar中的CANTP

【车载开发系列】AutoSar中的CANTP 【车载开发系列】AutoSar中的CANTP 【车载开发系列】AutoSar中的CANTP一. CANTP相关术语二. CANTP相关概念1&#xff09;单帧&#xff1a;SF(Single Frame)2&#xff09;首帧&#xff1a;FF(First Frame)3&#xff09;连续帧CF(Consecutive F…...

JUL日志

文章目录 JUL日志JUL日志讲解Properties配置文件编写日志配置文件Lombok快速开启日志Mybatis日志系统 JUL日志 如果使用System.out.println来打印信息&#xff0c;项目中存在大量的控制台输出语句&#xff0c;会显得很凌乱&#xff0c;而且日志的粒度是不够细的&#xff0c;假…...

ZZ308 物联网应用与服务赛题第G套

2023年全国职业院校技能大赛 中职组 物联网应用与服务 任 务 书 &#xff08;G卷&#xff09; 赛位号&#xff1a;______________ 竞赛须知 一、注意事项 1.检查硬件设备、电脑设备是否正常。检查竞赛所需的各项设备、软件和竞赛材料等&#xff1b; 2.竞赛任务中所使用…...

如何使用 vcpkg 编译Google-V8脚本引擎(ECMA/JavaScript)?

WIN32K下一键杀死所有同名进程命令行&#xff1a;taskkill /F /IM chrome.exe ############################## 1、准备 Visual Studio 2019 2、准备 Visual Studio 2022 3、安装 VC、MSBuild 编译集成环境 4、安装 Python 3.x&#xff0c;早期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)下载软件并进行安装&#xff0c;网站打不开多试几次或者找梯子。 二、macos系统里按“command 空格”搜索“终端”回车&#xff0c;启动终端程序。 三、执行下面命令&#xff0c;拉取docker镜像。 docker pull pch18/baota:clear pch…...

Java Lambda 表达式笔记

文章目录 Java Lambda 表达式语法Lambda 表达式实例Lambda表达式与函数式接口方法引用处理lambda表达式的接口 Java Lambda 表达式语法Lambda 表达式实例Lambda表达式与函数式接口方法引用处理lambda表达式的接口 Java Lambda 表达式 Lambda 表达式&#xff0c;也可称为闭包. …...

Flutter笔记:状态提升、控制器模式、GetX控制器和服务

Flutter笔记 状态提升、控制器模式、GetX控制器和服务 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/1…...

9.spark自适应查询-AQE之动态调整Join策略

目录 概述动态调整Join策略原理实战 动态优化倾斜的 Join原理实战 概述 broadcast hash join 类似于 Spark 共享变量中的广播变量&#xff0c;Spark join 如果能采取这种策略&#xff0c;那join 的性能是最好的 自适应查询AQE(Adaptive Query Execution) 动态调整Join策略 原…...

CentOs7 NAT模式连接网络

1.配置动态网络 1.1 检查主机网卡配置 检查主机的网络设置 进入控制面板&#xff0c;找到网络共享中心 查看适配器是否都已经开启 1.2 设置虚拟机的网络配置 打开虚拟机网络配置设置&#xff0c;对网卡VMnet8 进行设置 记住网关 全部选择应用&#xff0c;确定 1.3 设置…...

linux安装git

目录 声明 前言 正文 &#xff08;1&#xff09;下载git压缩包 &#xff08;2&#xff09;git压缩包解压 &#xff08;3&#xff09;解压完成后需要进行源码的编译操作 a.首先进去到解压后的文件目录中&#xff1a; b.执行&#xff1a; 编译的过程中可能遇到的问题&am…...

链栈(链式栈) 超详细实现(C 语言 + 逐行精讲)

前言栈&#xff08;Stack&#xff09; 是一种后进先出&#xff08;LIFO&#xff09;的线性数据结构。前面我们学习了顺序栈&#xff08;数组实现&#xff09;&#xff0c;今天我们学习它的兄弟 ——链栈&#xff08;链式栈&#xff09;。链栈 用单链表实现的栈它完美解决了顺序…...

Pretext:值得关注的文本排版引擎杆

一、语言特性&#xff1a;Java 26 与模式匹配进化 1.1 Java 26 语言级别支持 IDEA 2026.1 EAP 最引人注目的变化之一&#xff0c;就是新增 Java 26 语言级别支持。这意味着开发者可以提前体验和测试即将在 JDK 26 中正式发布的语言特性。 其中最重要的变化是对 JEP 530 的全面支…...

RGBW色彩转换器:嵌入式系统高保真白光增强方案

1. RGBW色彩转换器技术解析&#xff1a;面向嵌入式显示系统的高保真白光增强方案1.1 工程背景与设计动因在LED显示与智能照明嵌入式系统中&#xff0c;RGB三色LED驱动已成主流&#xff0c;但其在高亮度白光输出场景下存在固有缺陷&#xff1a;当需呈现高亮度中性白&#xff08;…...

Refined Now Playing:重塑网易云音乐播放体验的终极视觉革命

Refined Now Playing&#xff1a;重塑网易云音乐播放体验的终极视觉革命 【免费下载链接】refined-now-playing-netease &#x1f3b5; 网易云音乐沉浸式播放界面、歌词动画 - BetterNCM 插件 项目地址: https://gitcode.com/gh_mirrors/re/refined-now-playing-netease …...

Vue大屏自适应终极指南:v-scale-screen组件高效实战方案

Vue大屏自适应终极指南&#xff1a;v-scale-screen组件高效实战方案 【免费下载链接】v-scale-screen Vue large screen adaptive component vue大屏自适应组件 项目地址: https://gitcode.com/gh_mirrors/vs/v-scale-screen 在现代企业级数据可视化项目中&#xff0c;大…...

LFM2.5-1.2B-Thinking-GGUF辅助数学建模:从问题描述到MATLAB代码框架生成

LFM2.5-1.2B-Thinking-GGUF辅助数学建模&#xff1a;从问题描述到MATLAB代码框架生成 1. 数学建模的痛点与AI解决方案 数学建模是科研和工程领域的核心技能&#xff0c;但传统建模过程存在诸多挑战。许多研究者面临这样的困境&#xff1a;明明清楚问题描述&#xff0c;却卡在…...

软件语音助手中的唤醒词优化

软件语音助手中的唤醒词优化&#xff1a;让交互更自然高效 在智能设备普及的今天&#xff0c;语音助手已成为人们日常生活中不可或缺的伙伴。无论是查询天气、播放音乐&#xff0c;还是控制智能家居&#xff0c;唤醒词是用户与语音助手交互的第一道门槛。一个优秀的唤醒词不仅…...

SITS2026平台重构全记录:从单体Java商城到LLM+RAG驱动的AI原生电商,6周完成核心链路迁移并提升GMV 42%

第一章&#xff1a;SITS2026案例&#xff1a;AI原生电商平台实践 2026奇点智能技术大会(https://ml-summit.org) SITS2026是面向下一代电商基础设施的AI原生平台原型&#xff0c;由阿里云与浙江大学联合实验室在2024年Q4启动构建&#xff0c;于2025年Q2完成全链路灰度验证。该…...

Notepad--跨平台文本编辑器架构解析与技术实现深度剖析

Notepad--跨平台文本编辑器架构解析与技术实现深度剖析 【免费下载链接】notepad-- 一个支持windows/linux/mac的文本编辑器&#xff0c;目标是做中国人自己的编辑器&#xff0c;来自中国。 项目地址: https://gitcode.com/GitHub_Trending/no/notepad-- Notepad--作为一…...

Kubernetes Pod 日志持久化方案

Kubernetes Pod日志持久化方案解析 在云原生架构中&#xff0c;Kubernetes已成为容器编排的事实标准&#xff0c;但Pod的默认日志管理方式存在易丢失、难追溯的问题。日志作为故障排查、性能分析的重要依据&#xff0c;其持久化存储成为企业级应用的关键需求。本文将深入探讨几…...