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

洛谷 B3647：【模板】Floyd 算法

news 来源：原创 2025/6/27 0:54:32

【题目来源】
https://www.luogu.com.cn/problem/B3647

【题目描述】
给出一张由 n 个点 m 条边组成的无向图。
求出所有点对 (i,j) 之间的最短路径。

【输入格式】
第一行为两个整数 n，m，分别代表点的个数和边的条数。
接下来 m 行，每行三个整数 u，v，w，代表 u，v 之间存在一条边权为 w 的边。

【输出格式】
输出 n 行每行 n 个整数。
第 i 行的第 j 个整数代表从 i 到 j 的最短路径。

【输入样例】
4 4
1 2 1
2 3 1
3 4 1
4 1 1

【输出样例】
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0

【说明/提示】
对于 100% 的数据，n≤100，m≤4500，任意一条边的权值 w 是正整数且 1⩽w⩽1000。
数据中可能存在重边。

【算法分析】
● Floyd 算法‌（又称 Floyd-Warshall 算法）是一种用于求解‌所有顶点对之间最短路径‌的动态规划算法。它适用于‌带权有向图或无向图‌，可以处理‌正权边和负权边‌（但不能有负权环）。

● 本题数据中可能存在重边，若不处理，会有一个样例不过。
若有重边，处理方法是只保留权值最小的那条边。代码如下：

while(m--) {cin>>a>>b>>c;e[a][b]=min(e[a][b],c); //e[a][b]=c;e[b][a]=min(e[b][a],c); //e[b][a]=c;
}

● 若 e[i][i]<0，则存在负权环。

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int inf=0x3f3f3f3f;
int e[100][100];
int a,b,c;
int n,m;int main() {cin>>n>>m;for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {if(i==j) e[i][j]=0;else e[i][j]=inf;}}while(m--) {cin>>a>>b>>c;e[a][b]=min(e[a][b],c); //e[a][b]=c;e[b][a]=min(e[b][a],c); //e[b][a]=c;}for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j];for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {cout<<e[i][j]<<" ";}cout<<endl;}return 0;
}/*
in:
4 4
1 2 1
2 3 1
3 4 1
4 1 1out:
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0
*/

【参考文献】
https://blog.csdn.net/ahalei/article/details/22038539
https://www.cnblogs.com/CLGYPYJ/p/17586069.html

相关文章：

洛谷 B3647：【模板】Floyd 算法

【题目来源】 https://www.luogu.com.cn/problem/B3647 【题目描述】给出一张由 n 个点 m 条边组成的无向图。求出所有点对 (i,j) 之间的最短路径。【输入格式】第一行为两个整数 n，m，分别代表点的个数和边的条数。接下来 m 行，每行三…...

编程日记 2025/6/27 0:54:32

【25软考网工】第三章（4）生成树协议、广播风暴和MAC地址表震荡

目录一、生成树协议1. 生成树技术背景1）单链路上行存在单点故障2）二层环路问题3）二层环路问题——广播风暴实验验证广播风暴例题1：二层环路故障现象4）二层环路问题—— MAC地址表震荡实验验证 MAC地址表震荡的现象 2…...

编程日记 2025/6/27 0:33:07

解释器体系结构风格-笔记

解释器（Interpreter）是一种软件设计模式或体系结构风格，主要用于为语言（或表达式）定义其语法、语义，并通过解释器来解析和执行语言中的表达式。解释器体系结构风格广泛应用于编程语言、脚本语言、规则引擎、…...

编程日记 2025/5/29 12:12:57

删除新安装IBM Guardium Data Protection 12.1的baltimorecybertrustroot证书

登录web console，会显示 baltimorecybertrustroot证书过期警告。采用下面的命令删除过期证书就可消除警告。 collector02.cpd.com> delete certificate keystore Select an alias from the list below to delete the corresponding certificate. Alias List:…...

编程日记 2025/6/23 1:49:21

反序列化漏洞1

一、PHP类与对象 1. 类概念理解: 类是共享相同结构和行为的对象的集合，可以理解为特征的提取。例如将耳朵长、尾巴短、红眼睛、吃胡萝卜、蹦跳行走的动物特征抽象为"兔子"类。代码结构: 使用class关键字定义类类名遵循大驼峰命名法包含成员变量(属性)和…...

编程日记 2025/6/22 19:26:24

正则表达式三剑客之——awk命令

目录一.什么是awk 二.awk的语法格式 1.选项 2. 模式（Pattern） 3. 操作（Action） 4. 输入文件（file） 5.总结三.awk的工作原理 1. 逐行扫描输入 2. 匹配模式 1.正则表达式： 2.逻辑表…...

编程日记 2025/6/27 0:34:30

施磊老师基于muduo网络库的集群聊天服务器(七)

文章目录数据表字符集问题支持中文和英文**为什么使用 utf8mb4？** 推荐查看整个表, 再单独修改客户端群组功能创建群组添加群组群组聊天接收在线群组消息接收离线群组消息补充服务器事件处理器补充服务器查询群组列表问题解决测试目前报错总结目前为止最恶心的错…...

编程日记 2025/5/29 11:29:33

多模态（3）：实战 GPT-4o 视频理解

最近，OpenAI 团队的 GPT-4o 模型，在多模态方面的能力有了大幅提升，这次我们就使用 GPT-4o 完成一个视频理解的实战。 1. 环境搭建 1.1 安装 FFmpeg 做视频处理，我们需要用到 FFmpeg 这款功能强大的开源多媒体处理工具。FFmpeg…...

编程日记 2025/6/26 11:25:58

基于python实现一个二维图片的路径规划问题

一、场景基于如下的一个楼层平面图，假设有几个预置的点（实际项目中可能是动态的点，比如找车位，找工位），做路径规划，并画在平面图上二、方案 1.准备平面室内图可以自己用QGIS/cad等其他方式…...

编程日记 2025/6/26 10:28:22

云服务器centos 安装hadoop集群

百度搜索云服务器centos 安装hadoop 创建Hadoop用户 sudo useradd hadoop -m -s /bin/bash sudo passwd hadoop 123456 下载Hadoop wget https://mirrors.tuna.tsinghua.edu.cn/apache/hadoop/common/hadoop-3.2.4/hadoop-3.2.4.tar.gz 解压并移动Hadoop到指定目录 tar …...

编程日记 2025/6/23 11:49:16

【k8s】sidecar边车容器

一、Sidecar 模式简介 Sidecar 模式是一种常见的微服务架构设计模式。它通过将附加功能或服务与主应用程序部署在同一容器或主机上，从而实现对主应用程序的增强和扩展。Sidecar 的名称来源于摩托车的边车，它与摩托车紧密相连，为主车提供额外…...

编程日记 2025/6/25 22:44:27

Web漏洞--XSS之订单系统和Shell箱子

本文主要内容手法 XSS平台使用 XSS工具使用 XSS结合其他漏洞 XSS具体使用场景某订单系统XSS盲打_平台某Shell箱子系统XSS盲打_工具 [1]订单系统经典案例第一个简易攻击流程（订单系统）：通过平台完成XSS跨站之后&a…...

编程日记 2025/6/23 16:43:27

# 构建词汇表：自然语言处理中的关键步骤

构建词汇表：自然语言处理中的关键步骤在自然语言处理（NLP）任务中，词汇表（Vocabulary）是文本数据预处理的核心组件之一。它将文本中的单词或字符映射为数值索引，从而让计算机能够理解和处理语言…...

编程日记 2025/6/25 22:41:55

新！在 podman-machine-default 中安装 CUDA、cuDNN、Anaconda、PyTorch 等并验证安装

#工作记录一、前言在 Windows 系统开发环境中，Podman Desktop 凭借强大的容器管理与 WSL-Linux 子系统集成能力备受开发者关注。其中，podman-machine-default 是 Podman Desktop 安装后自带的默认 WSL-Fedora 子系统，支持与显卡通信&am…...

编程日记 2025/6/21 20:07:47

python_BeautifulSoup提取html中的信息

目录描述： 过程： step one 下载html网页到本地 step two 提取html信息 list_con soup.select(.list-con) [0] li_list list_con.find_all(li) a li.find(span).find(a) title a.get(title) url a.get(href) span li.find(span).find(spa…...

编程日记 2025/6/26 7:23:36

pcd2pgm的launch文件实现

1.新建工作空间和克隆代码 mkdir -p pcd2pgm_launch/src && cd pcd2pgm_launch/src git clone https://github.com/Hinson-A/pcd2pgm_package 2. 编译 cd .. catkin_make -j4 3.修改launch 在launch文件目录下，可以用gedit 打开launch文件&#xff0c…...

编程日记 2025/5/8 17:08:32

Vue里面elementUi-aside 和el-main不垂直排列

先说解决方法 main.js少导包 import element-ui/lib/theme-chalk/index.css; //加入此行即可问题复现排查了一个小时终于找出来问题了，建议导包去看官方的文档，作者就是因为看了别人的导包流程导致的问题导包官网地址Element UI导包快速入门...

编程日记 2025/6/22 12:25:28

论文阅读：2024 ACL ArtPrompt: ASCII Art-based Jailbreak Attacks against Aligned LLMs

总目录大模型安全相关研究：https://blog.csdn.net/WhiffeYF/article/details/142132328 Artprompt: Ascii art-based jailbreak attacks against aligned llms https://www.doubao.com/chat/3846685176618754 https://arxiv.org/pdf/2402.11753 https://github…...

编程日记 2025/6/24 21:26:03

项目maven版本不一致导致无法下载

路程：打开一个新项目发现，maven加载不了报错： Error running ‘dataManage [clean]’ No valid Maven installation found. Either set the home directory in the configuration dialog or set the M2_HOME environment variable on your s…...

编程日记 2025/6/24 12:40:22

论文阅读：2024 NeurIPS Group Robust Preference Optimization in Reward-free RLHF

Group Robust Preference Optimization in Reward-free RLHF https://www.doubao.com/chat/3870738843518978 https://arxiv.org/pdf/2405.20304 速览研究动机传统RLHF忽视群体偏好差异，导致模型对少数群体表现不佳，需提升群体鲁棒性。研究问题如…...

编程日记 2025/6/26 4:16:33

数据可视化平台产品介绍及功能特色

数据可视化平台是一款适用于高校教学和各领域企业的零门槛可视化工具，能够解决高校数据分析与可视化类课程教学、实训问题。平台通过浏览器即可访问，无需安装客户端。平台内置公式编辑器与指标构建器，学生可通过四则运算、分组聚合等方式衍生…...

编程日记 2025/6/25 20:54:17

MySQL索引优化、SQL分析与运行原理 - Java架构师面试实战

MySQL索引优化、SQL分析与运行原理 - Java架构师面试实战第一轮提问面试官：马架构，请问您对MySQL的B树索引有什么理解？ 马架构：B树是一种平衡多路查找树，所有的数据节点都存储在叶子节点上。相比于B树&#xff0c…...

编程日记 2025/6/25 22:23:55

C++学习：六个月从基础到就业——STL：函数对象与适配器

C学习：六个月从基础到就业——STL：函数对象与适配器本文是我C学习之旅系列的第二十九篇技术文章，也是第二阶段"C进阶特性"的第八篇，主要介绍C STL中的函数对象与适配器。查看完整系列目录了解更多内容。引言在前面的…...

编程日记 2025/6/24 7:16:10

Linux基础篇、第四章_02磁盘及分区管理fdisk 和 gdisk

题目：Linux 磁盘及分区管理版本号: 1.0,0 作者: 老王要学习日期: 2025.04.25 适用环境: Centos7 文档说明本教程适用于 Centos7 环境，详细介绍 Linux 磁盘及分区管理操作。包含虚拟机添加磁盘的关机与开机添加方法、MBR 和 GPT 两种分区方式特点、…...

编程日记 2025/6/25 1:22:23

火山云的市场竞争

火山云是字节跳动旗下的云计算服务，对吧？那它的竞争对手应该包括国内外的大型云服务提供商。首先，国际市场上，像AWS、Azure、Google Cloud这些巨头肯定是大头。国内的话，阿里云、腾讯云、华为云这些应该都是主要的竞争…...

编程日记 2025/6/24 10:56:28

创建型设计模式之：简单工厂模式、工厂方法模式、抽象工厂模式、建造者模式和原型模式

创建型设计模式之：简单工厂模式、工厂方法模式、抽象工厂模式、建造者模式和原型模式 （一）简单工厂模式简单工厂模式将对象的实例化过程封装到一个工厂类中，根据输入的条件创建不同类型的对象。角色划分： 抽象产品…...

编程日记 2025/6/24 1:48:46

【Linux内核设计与实现】第三章——进程管理01

文章目录 1. 引言2. 进程&线程——概念3. 进程控制块/进程描述符(PCB)4. 进程内核栈（Kernel Stack）4.1. 进程内核栈的定义4.2. thread_info 体系结构相关进程描述4.3. 定位进程描述符(task_struct)和内核栈以及内核栈指针的问题 5. 进程 ID&#xff…...

编程日记 2025/6/23 12:45:46

正大模型视角下的市场结构判断逻辑

正大模型视角下的市场结构判断逻辑在多数交易策略中，结构识别往往先于方向判断。以正大的数据研判风格为例，其核心逻辑是：价格行为不能孤立解读，必须结合时间与成交效率来判断当前结构的有效性。例如，一个上涨过程&…...

编程日记 2025/6/20 9:31:25

4.25学习——文件上传之00截断

继昨天学习的基础文件上传内容，进一步学习文件上传的绕过方式 00截断绕过原理：00截断是操作系统层的漏洞，由于操作系统是C语言或汇编语言编写的，这两种语言在定义字符串时，都是以\0（即0x00）作…...

编程日记 2025/5/27 13:29:41

黑马Redis（三）黑马点评项目

优惠卷秒杀一、全局唯一ID 基于Redis实现全局唯一ID的策略： Component RequiredArgsConstructor public class RedisIdWorker {private static final Long BEGIN_TIMESTAMP1713916800L;private static final int COUNT_BITS 32;Resourceprivate final StringRed…...

编程日记 2025/6/23 18:13:11

dedecms织梦arclist标签noflag属性过滤多个参数

织梦dedecms系统arclist标签noflag属性默认是只能过滤一个参数，比如过滤推荐是noflagc，过滤有图片的文章是noflagc，在模板制作过程中，有时候我们为了seo和避免重复，需要过滤多个参数。今天小编就来跟大家讲讲织梦dedec…...

编程日记 2025/6/23 11:30:22

Jira、PingCode、Redmine等18款缺陷管理工具对比评测

本文主要介绍了以下：1. PingCode; 2. Worktile; 3. Jira; 4. Bugzilla; 5. TAPD; 6. 码云; 7. Redmine; 8. Trac; 9. 蓝鲸智云; 10. 阿里云效等等18款缺陷管理工具。在现代软件开发和项目管理中，缺陷管理工具扮演着至关重要的角色。随着企业对软件质量的…...

编程日记 2025/5/17 20:12:00

京东以图搜图（拍立淘）API接口返回参数详解

京东以图搜图（拍立淘）API接口的返回参数通常以结构化JSON格式呈现，涵盖商品基础信息、相似度评分、库存状态及扩展字段，以下为关键参数详解及使用建议： 一、核心返回参数解析状态标识类 status：请求状态…...

编程日记 2025/6/22 11:28:53

LSTM+KNN - 多元数据异常检测！

大家好！我是我不是小 upper~ 今天想和大家分享一个超实用的案例：如何通过 LSTM 与 KNN 实现多元数据异常检测。想象一下，在工厂的智能化监控场景中，各类传感器实时采集着温度、湿度、压力等海量数据。我们的目标，就是从中精准识别出设备潜在故障等异常情况。 LSTM 作为时…...

编程日记 2025/6/25 8:16:54

OpenHarmony之电源管理子系统公共事件定义

OpenHarmony之电源管理子系统公共事件定义电源管理子系统面向应用发布如下系统公共事件，应用如需订阅系统公共事件，请参考公共事件接口文档。 COMMON_EVENT_BATTERY_CHANGED 表示电池充电状态、电平和其他信息发生变化的公共事件的动作。值&#x…...

编程日记 2025/6/24 19:38:34

angular 实现可编辑可选择复制的表格

这个实现的核心就是ag-grid 当然有类似的库就不必多说，React, Vue和纯h5类似。简单贴一下代码 1.首先是h5部分，就一个id为supply-chain-material-grid-table的div，记住要设置高度 <div class"dki-supply-chain-page-body">…...

编程日记 2025/6/26 20:50:58

组织用户数统计实现

# 完整的组织用户数统计实现完整的组织用户数统计实现，包括模拟SQL查询、完整的Java代码实现以及详细解释。 ## 1. 模拟SQL查询假设我们有一个组织表(organization)和用户表(user)，以下是模拟查询SQL： sql -- 获取各组织及其用户数量&a…...

编程日记 2025/6/25 9:32:44

天机学堂day10作业，完善兑换优惠券功能

UserCouponServiceImpl /*** 兑换码兑换优惠券* param code*/TransactionalOverridepublic void exchangeCoupon(String code) {//1、校验code是否为空if (StringUtils.isBlank(code)) {throw new BadRequestException("非法参数！");}//2、解析兑换码&…...

编程日记 2025/6/23 14:30:00

Python编程的真谛：超越语法，理解编程本质

你是否也曾陷入这样的误区：学了无数的 Python 语法、刷了几十套题，写起代码却仍然卡顿、举步维艰？这时候你才发现，真正阻碍进步的，从不是语法，而是你对“编程本质”的理解。如果你只是死记硬背Python的语…...

编程日记 2025/6/24 18:52:03

C语言函数补充

目录 static和extern函数 1.static和extern函数 static和extern都是C语言中的关键字 static 是静态的的意思，可以用来: - 修饰局部变量- 修饰全局变量- 修饰函数 extern 是用来声明外部符号的。在讲解 static 和 extern 之前再讲一下: 作用域和生命周期。 …...

编程日记 2025/6/25 22:15:33

【AI图像创作变现】04实操路径—插图/绘本/创意图集

引言如果说头像是“一个角色的起点”，那么插图、绘本和图集就是“这个角色能走多远”。相比于头像这种单图任务，插图类创作更强调批量性、叙事性与风格统一性，它既可以承载故事，也可以构成一套完整的内容产品结构。这类任务特…...

编程日记 2025/6/24 20:41:55

Lesar: 面向 Lustre/Scade 语言的形式化模型检查工具

在《同步反应式系统》的第一课中，介绍了同步数据流语言 Lustre 生态中的形式化模型检查器 Lesar 的用法。Lesar 可对 lustre v4 语言以及 Scade 语言中部分数据流核心特性进行模型检查。 Lesar 介绍 Lesar 是 Verimag 研发维护的形式化方法模型检查工具。该工具的理…...

编程日记 2025/6/1 17:53:06

告别 “幻觉” 回答：RAG 中知识库与生成模型的 7 种对齐策略

一、引言大语言模型（LLM）在文本生成领域展现出惊人能力，但 “幻觉” 问题（生成虚构或偏离事实的内容）始终是落地应用的核心挑战。检索增强生成（RAG）通过将外部知识库与 LLM 结合，形…...

编程日记 2025/6/25 7:45:26

【Web应用服务器_Tomcat】一、Tomcat基础与核心功能详解

在 Java Web 应用开发领域，Apache Tomcat 是一座不可或缺的基石。作为一款开源、轻量级的 Servlet 容器和 Web 服务器，Tomcat 以其稳定可靠、易于部署和高度可定制性，被广泛应用于各类 Web 应用的部署与运行。一、Tomcat 简介 Tomcat 是…...

编程日记 2025/5/10 17:01:00

Cesium实现地形可视域分析

Cesium实现可视化分析一、地形可视域主要实现技术（Ray + 地形碰撞检测） Cesium 本身的 Ray 类可以用来执行非常精确的射线检测，我们可以结合地形高度（sample）来逐点检测光线是否与 terrain 相交，从而判断是否可见。 1.1 优势实时判断每条射线是否被 terrain 遮挡地形…...

编程日记 2025/6/20 14:40:01

Java—— 常见API介绍第五期

JDK8以后新增的时间相关类 Date类ZoneId：时区Instant：时间戳ZoneDateTime：带时区的时间日期格式化类 SimpleDateFormat DateTimeFormatter：用于时间的格式化和解析日历类 Calendar LocalDate：年、月、日LocalTime…...

编程日记 2025/6/24 19:53:50

ViewPager FragmentPagerAdapter在系统杀死应用后重建时UI不刷新的问题

解决方案通过重写getItemId方法，返回Fragment的hashCode： Override public long getItemId(int position) {/*** 恢复状态重建时，新的 Fragment 不刷新UI。* 原因：instantiateItem 中通过 mFragmentManager.findFragmentByTag(…...

编程日记 2025/6/25 18:04:07

第3讲、大模型如何理解和表示单词：词嵌入向量原理详解

1. 引言大型语言模型（Large Language Models，简称LLM）如GPT-4、Claude和LLaMA等近年来取得了突破性进展，能够生成流畅自然的文本、回答复杂问题、甚至编写代码。但这些模型究竟是如何理解人类语言的？它们如何表示和处…...

编程日记 2025/6/26 1:23:05

关于STM32f1新建工程

创建文件夹首先创建一个存放工程的文件夹，建议建立在D，E盘新建工程在kiel5里面找到刚刚建立的文件夹，然后在此文件夹里面新建一个文件夹用来存放本次工程，文件夹可以根据工程内容所编写，然后给自己工程也就是…...

编程日记 2025/6/24 11:10:36

Linux：进程间通信---匿名管道

文章目录 1. 进程间通信1.1 什么是进程间通信？1.2 为什么进程要进行进程间通信？1.3 怎么实现进程间通信？ 2. 匿名管道2.1 匿名管道的原理2.2 匿名管道的系统接口2.3 匿名管道的使用2.4 匿名管道的运用场景序：在上一篇文章中我们知…...

编程日记 2025/6/26 20:36:09