当前位置: 首页 > 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…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

电脑桌面太单调,用Python写一个桌面小宠物应用。

下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡&#xff0c;可以响应鼠标点击&#xff0c;并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...

拟合问题处理

在机器学习中&#xff0c;核心任务通常围绕模型训练和性能提升展开&#xff0c;但你提到的 “优化训练数据解决过拟合” 和 “提升泛化性能解决欠拟合” 需要结合更准确的概念进行梳理。以下是对机器学习核心任务的系统复习和修正&#xff1a; 一、机器学习的核心任务框架 机…...