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

C语言-算法-最短路

【模板】Floyd

题目描述

给出一张由 n n n 个点 m m m 条边组成的无向图。

求出所有点对 ( i , j ) (i,j) (i,j) 之间的最短路径。

输入格式

第一行为两个整数 n , m n,m n,m,分别代表点的个数和边的条数。

接下来 m m m 行,每行三个整数 u , v , w u,v,w u,v,w,代表 u , v u,v u,v 之间存在一条边权为 w w w 的边。

输出格式

输出 n n n 行每行 n n n 个整数。

i i i 行的第 j j j 个整数代表从 i i i j j j 的最短路径。

样例 #1

样例输入 #1

4 4
1 2 1
2 3 1
3 4 1
4 1 1

样例输出 #1

0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0

提示

对于 100 % 100\% 100% 的数据, n ≤ 100 n \le 100 n100 m ≤ 4500 m \le 4500 m4500,任意一条边的权值 w w w 是正整数且 1 ⩽ w ⩽ 1000 1 \leqslant w \leqslant 1000 1w1000

数据中可能存在重边。

代码实现

#include <stdio.h>
void floyd(); // Floyd算法
#define MAX 10000
#define INF 0x3f3f3f3f // 无穷大
int n, m;
int g[MAX][MAX];int main()
{int i, j, u, v, w;scanf("%d %d", &n, &m); // 输入点的个数和边的条数for (i = 1; i <= n; i++) // 初始化图的邻接矩阵{for (j = 1; j <= n; j++){// 对角线上的元素为0,其他元素为无穷大if (i == j){g[i][j] = 0;}else{g[i][j] = INF;}}}for (i = 0; i < m; i++){scanf("%d %d %d", &u, &v, &w);if (g[u][v] > w) // 由于可能存在重边,我们需要保留权值最小的那条边{g[u][v] = w;g[v][u] = w;}}floyd(); // 执行Floyd算法for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){printf("%d ", g[i][j]); }printf("\n");}return 0;
}void floyd()
{int i, j, k; // i和j是起始和结束节点,k是中间节点for (k = 1; k <= n; k++){for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){// 如果通过k节点的路径比当前i到j的路径短,那么更新g[i][j]if (g[i][k] != INF && g[k][j] != INF && g[i][j] > g[i][k] + g[k][j]){g[i][j] = g[i][k] + g[k][j];}}}}
}

无向图的最小环问题

题目描述

给定一张无向图,求图中一个至少包含 3 3 3 个点的环,环上的节点不重复,并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中,你需要输出最小的环的边权和。若无解,输出 No solution.

输入格式

第一行两个正整数 n , m n,m n,m 表示点数和边数。

接下来 m m m 行,每行三个正整数 u , v , d u,v,d u,v,d,表示节点 u , v u,v u,v 之间有一条长度为 d d d 的边。

输出格式

输出边权和最小的环的边权和。若无解,输出 No solution.

样例 #1

样例输入 #1

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

样例输出 #1

61

提示

样例解释:一种可行的方案: 1 − 3 − 5 − 2 − 1 1-3-5-2-1 13521

对于 20 % 20\% 20% 的数据, n , m ≤ 10 n,m \leq 10 n,m10

对于 60 % 60\% 60% 的数据, m ≤ 100 m\leq 100 m100

对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 100 1\le n\leq 100 1n100 1 ≤ m ≤ 5 × 1 0 3 1\le m\leq 5\times 10^3 1m5×103 1 ≤ d ≤ 1 0 5 1 \leq d \leq 10^5 1d105

无解输出包括句号。

代码

相关文章:

C语言-算法-最短路

【模板】Floyd 题目描述 给出一张由 n n n 个点 m m m 条边组成的无向图。 求出所有点对 ( i , j ) (i,j) (i,j) 之间的最短路径。 输入格式 第一行为两个整数 n , m n,m n,m&#xff0c;分别代表点的个数和边的条数。 接下来 m m m 行&#xff0c;每行三个整数 u …...

【操作系统·考研】I/O管理概述

1.I/O设备 1.1 块设备 信息交换以数据块为单位&#xff0c;它属于有结构设备。 块设备传输速率较高&#xff0c;可寻址&#xff0c;且可对该设备随机地的读写。 栗子&#x1f330;&#xff1a;磁盘。 1.2 字符设备 信息交换以字符为单位&#xff0c;属于无结构类型。 字符…...

Linux实验记录:使用vsftpd服务传输文件

前言&#xff1a; 本文是一篇关于Linux系统初学者的实验记录。 参考书籍&#xff1a;《Linux就该这么学》 实验环境&#xff1a; VmwareWorkStation 17——虚拟机软件 RedHatEnterpriseLinux[RHEL]8——红帽操作系统 备注&#xff1a; 为了解决在多样复杂的设备之间解决传…...

实习|基于SSM的实习管理系统设计与实现(源码+数据库+文档)

实习管理系统目录 目录 基于SSM的实习管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员功能介绍 &#xff08;1&#xff09;管理员登录 &#xff08;2&#xff09;实训方向管理 &#xff08;3&#xff09;公告信息管理 &#xff08;4&#xff0…...

商品介绍和规则参数图片映射和IP设置

虚拟路径映射配置&#xff1a; registry.addResourceHandler("/image/productIntroImgs/**").addResourceLocations("file:D:\\java1234-mall-v3\\productIntroImgs\\");registry.addResourceHandler("/image/productParaImgs/**").addResourceL…...

【React】前端React 代码中预览展示excel文件

封装了ExcelView来展示excel文件&#xff0c;支持显示loading 1.安装依赖 npm i js-preview/excel源码 import React, { useEffect, useRef, useState } from react import jsPreviewExcel, { JsExcelPreview } from js-preview/excel import js-preview/excel/lib/index.cs…...

QButtonGroup使用介绍

一、简介 QButtonGroup是PyQt5库中的一个组件&#xff0c;主要用于组织和管理一组按钮。通过QButtonGroup&#xff0c;可以方便地实现单选框或多选框功能&#xff0c;统一处理按钮的信号&#xff0c;并且可以为按钮分组设定ID以进行识别。 1、原始工程 from PyQt5.Qt import …...

最近nvm安装报错的原因找到了——npm原淘宝镜像正式到期!

前言 &#x1f4eb; 大家好&#xff0c;我是南木元元&#xff0c;热爱技术和分享&#xff0c;欢迎大家交流&#xff0c;一起学习进步&#xff01; &#x1f345; 个人主页&#xff1a;南木元元 目录 背景 错误原因 问题排查 淘宝镜像 证书到期 问题解决 结语 背景 我们…...

docker面试问题二

如何防止Docker容器中的漏洞和攻击&#xff1f; 防止Docker容器中的漏洞和攻击是一个多层次、多方面的任务&#xff0c;涉及从镜像构建、容器运行到网络安全的整个生命周期。以下是一些关键措施&#xff1a; 使用官方和受信任的镜像&#xff1a; 总是从官方源或受信任的第三方…...

嵌入式中C 语言中的三块技术难点

C 语言在嵌入式学习中是必备的知识&#xff0c;甚至大部分操作系统都要围绕 C 语言进行&#xff0c;而其中有三块技术难点&#xff0c;几乎是公认级别的“难啃的硬骨头”。 今天就来带你将这三块硬骨头细细拆解开来&#xff0c;一定让你看明白了。 0x01 指针 指针是公认最难理…...

基于SSM的个性化旅游攻略定制系统设计与实现(有报告)。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的个性化旅游攻略定制系统设计与实现&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xf…...

[React源码解析] Fiber (二)

在React15及以前, Reconciler采用递归的方式创建虚拟Dom, 但是递归过程不可以中断, 如果组件的层级比较深的话, 递归会占用线程很多时间, 那么会造成卡顿。 为了解决这个问题, React16将递归的无法中断的更新重构为异步的可中断更新, Fiber架构诞生。 文章目录 1.Fiber的结构2…...

Nginx 多项目部署,vue刷新404 解决方案

网上找的资料大多都解决不了&#xff0c;废话不多说直接告诉你解决方法。 环境是 TP6 VUE前端官网 VUE 后台管理 部署 两个项目 刷新 404 解决方案 Nginx 配置 直接贴图 如果解决了&#xff0c;给我顶起来&#xff0c;让更多人 快速的解决。...

[C++]类和对象(中)

一:类的六个默认成员函数 如果一个类中什么成员都没有&#xff0c;简称为空类。空类中并不是什么都没有&#xff0c;任何类在什么都不写时&#xff0c;编译器会自动生成以下6个默认成员函数。默认成员函数&#xff1a;用户没有显式实现&#xff0c;编译器会生成的成员函数称为…...

Kubernetes operator(五)api 和 apimachinery 篇

云原生学习路线导航页&#xff08;持续更新中&#xff09; 本文是 Kubernetes operator学习 系列第五篇&#xff0c;主要对 k8s.io/api 和 k8s.io/apimachinery 两个项目 进行学习基于 kubernetes v1.24.0 代码分析Kubernetes operator学习系列 快捷链接 Kubernetes operator&a…...

接口自动化测试中解决接口间数据依赖

在实际的测试工作中&#xff0c;在做接口自动化测试时往往会遇到接口间数据依赖问题&#xff0c;即API_03的请求参数来源于API_02的响应数据&#xff0c;API_02的请求参数又来源于API_01的响应数据。 因此通过自动化方式测试API_03接口时&#xff0c;需要预先请求API_02接口&a…...

七、测试计划(软件工程)

1&#xff0e;引言 1.1编写目的 1.2项目背景 1.3定义 1.4参考资料 2&#xff0e;任务概述 2.1目标 2.2运行环境 2.3需求概述 2.4条件与限制 3&#xff0e;计划 3.1测试方案 3.2测试项目 3.3测试准备 3.4测试机构及人员 4&#xff0e;测试项目说明…...

ElementUI Form:Checkbox 多选框

ElementUI安装与使用指南 Checkbox 多选框 点击下载learnelementuispringboot项目源码 效果图 el-checkbox.vue &#xff08;Checkbox 多选框&#xff09;页面效果图 项目里el-checkbox.vue代码 <script> const cityOptions [上海, 北京, 广州, 深圳] export def…...

如何统一监听Vue组件报错

window.onerror 全局监听所有JS错误&#xff0c;包括异步错误但是它是JS级别的&#xff0c;识别不了Vue组件信息&#xff0c;Vue内部的错误还是用Vue来监听捕捉一些Vue监听不到的错误 errorCaptured生命周期 监听所有下级组件的错误返回false会阻止向上传播到window.onerror …...

python爬虫4

#1.练习 # &#xff08;1&#xff09; 获取网页的源码 # &#xff08;2&#xff09; 解析 解析的服务器响应的文件 etree.HTML # (3) 打印 import urllib.request urlhttps://www.baidu.com/ headers {User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...