C++ Floyd求最短路 Floyd算法(多源汇最短路)

给定一个 n
个点 m
条边的有向图,图中可能存在重边和自环,边权可能为负数。

再给定 k
个询问,每个询问包含两个整数 x
和 y
,表示查询从点 x
到点 y
的最短距离,如果路径不存在,则输出 impossible。

数据保证图中不存在负权回路。

输入格式
第一行包含三个整数 n,m,k

接下来 m
行,每行包含三个整数 x,y,z
,表示存在一条从点 x
到点 y
的有向边,边长为 z

接下来 k
行,每行包含两个整数 x,y
,表示询问点 x
到点 y
的最短距离。

输出格式
共 k
行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出 impossible。

数据范围
1≤n≤200
,
1≤k≤n2

1≤m≤20000
,
图中涉及边长绝对值均不超过 10000

输入样例:
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例:
impossible
1
在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 210;
int n, m, k;
int d[N][N];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]);
}int main ()
{scanf("%d%d%d", &n, &m, &k);memset(d, 0x3f, sizeof(d));for(int i = 1; i <= n; i ++ )for(int j = 1; j <= n; j ++ )if(i == j) d[i][j] = 0;for(int i = 0; i < m; i ++ ){int x, y, z;scanf("%d%d%d", &x, &y, &z);d[x][y] = min(d[x][y], z);}floyd();while(k -- ){int x, y;scanf("%d%d", &x, &y);int dist = d[x][y];if(dist > 0x3f3f3f3f / 2)printf("impossible\n");elseprintf("%d\n", dist);}return 0;
}

邻接矩阵存储,3重循环遍历完,邻接矩阵直接就是最短距离。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/270323.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

过于老旧的pytorch_ssim包 请从github下载源码

有些冷门算法真的不要随便pip&#xff0c;有可能下载到史前版本…最好还是找源代码 汗 今天要用到SSIM损失函数&#xff0c;从网上简单看了一下原理就想测试一下&#xff0c;偷了一下懒就直接在命令行输入pip install pytorch_ssim了&#xff0c;结果报了一堆错误&#xff08;汗…

Python(NetOps)前传-网络设备开局配置

背景 我们知道用Python在cli配置网络设备的前提是&#xff1a; 网络设备与Python主机网络可达网络设备已开启并完成ssh相关配置 目标 本文已华为S5720S-52P-LI-AC交换机为例&#xff0c;完成&#xff1a; 完成网络设备开局配置&#xff1b;用Python脚本验证ssh登录 配置 …

人人都写过的6个bug

大家好&#xff0c;我是知微。 程序员写bug几乎是家常便饭&#xff0c;也是我们每个人成长过程中难以避免的一部分。 为了缓解这份“尴尬”&#xff0c;今天想和大家分享一些曾经都会遇到过的bug&#xff0c;让我们一起来看看这些“经典之作”。 1、数组越界 #include <…

【单片机学习的准备】

文章目录 前言一、找一个视频是二、画图软件三、装keil5 仿真protues总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 项目需要&#xff1a; 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、找一个视频是 https://www.b…

MongoDB聚合运算符:$count

文章目录 语法使用举例在$group阶段中使用在$setWindowFields阶段使用 $count聚合运算符返回分组中文档的数量。从5.0开始支持。 语法 { $count: { } }$count不需要参数 使用 $count可以用于下列聚合阶段&#xff1a; $bucket$bucket$group$setWindowFields 在$group阶段中…

基于springboot+vue的校园网上店铺

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

MySQL 学习笔记(基础篇 Day1)

「写在前面」 本文为黑马程序员 MySQL 教程的学习笔记。本着自己学习、分享他人的态度&#xff0c;分享学习笔记&#xff0c;希望能对大家有所帮助。 目录 0 课程介绍 1 MySQL 概述 1.1 数据库相关概念 1.2 MySQL 数据库 2 SQL 2.1 SQL 通用语法 2.2 SQL 分类 2.3 DDL 2.4 图形…

计算机网络-第2章 物理层

本章内容&#xff1a;物理层和数据通信的概念、传输媒体特点&#xff08;不属于物理层&#xff09;、信道复用、数字传输系统、宽带接入 2.1-2.2 物理层和数据通信的概念 物理层解决的问题&#xff1a;如何在传输媒体上传输数据比特流&#xff0c;屏蔽掉传输媒体和通信手段的差…

【python高级编程教程】笔记(python教程、python进阶)第三节:(1)多态与鸭子类型(Polymorphism and Duck Typing)

参考文章1&#xff1a;【比刷剧还爽】清华大佬耗时128小时讲完的Python高级教程&#xff01;全套200集&#xff01;学不会退出IT界&#xff01; 参考文章2&#xff1a;清华教授大力打造的Python高级核心技术&#xff01;整整100集&#xff0c;强烈建议学习&#xff08;Python3…

Python 开发图形界面程序

用 Python 语言开发图形界面的程序&#xff0c;有2种选择&#xff1a; Tkinter 基于Tk的Python库&#xff0c;这是Python官方采用的标准库&#xff0c;优点是作为Python标准库、稳定、发布程序较小&#xff0c;缺点是控件相对较少。 PySide2/PySide6 基于Qt 的Python库&#x…

JMeter VS RunnerGo :两大主流性能测试工具对比

说起JMeter&#xff0c;估计很多测试人员都耳熟能详。它小巧、开源&#xff0c;还能支持多种协议的接口和性能测试&#xff0c;所以在测试圈儿里很受欢迎&#xff0c;也是测试人员常用的工具&#xff0c;不少企业也基于JMeter建立起自己的自动化测试能力&#xff0c;提升工作效…

VMware虚拟机安装Linux

1.新建虚拟机 2. 安装操作系统 等待 选择中文 点软件选择 选择下面的GNOME桌面 禁用KDUMP 点进安装位置&#xff0c;点完成就可以了 网络连接&#xff0c;右上角打开 开始安装&#xff0c;输入ROOT密码&#xff0c;创建用户 点击重启&#xff0c;等待 重启完成之后出现下面的界…

javaWebssh在线授课辅导系统myeclipse开发mysql数据库MVC模式java编程计算机网页设计

一、源码特点 java ssh在线授课辅导系统是一套完善的web设计系统&#xff08;系统采用ssh框架进行设计开发&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用 B/S模式开发。开发环境为TOMCAT7.…

PaddleOCR CPU 文本文字识别 docker部署

需求&#xff1a; 需要把所有滑块图片的数据文字提取出来 启动服务 mkdir paddle cd paddle docker run -itd --name ppocr -v $PWD:/paddle --networkhost -it registry.baidubce.com/paddlepaddle/paddle:2.1.3-gpu-cuda10.2-cudnn7 /bin/bash docker exec -it ppocr bash …

重装显卡驱动记录

重装显卡驱动记录 任务记录现状描述执行情况 任务 晚上回来&#xff0c;开电脑&#xff0c;发现总是进不去系统&#xff08;这个情况我经常见&#xff09;&#xff0c;但偶尔进系统&#xff0c;识别不了我的外接屏&#xff08;这个第一次见&#xff09;。来来回回重启了1h多了…

JVM内部世界(内存划分,类加载,垃圾回收)

&#x1f495;"Echo"&#x1f495; 作者&#xff1a;Mylvzi 文章主要内容&#xff1a;JVM内部世界(内存划分,类加载,垃圾回收) 关于JVM的学习主要掌握三方面: JVM内存区的划分类加载垃圾回收 一.JVM内存区的划分 当一个Java进程开始执行时,JVM会首先向操作系统申…

18 easy 104. 二叉树的最大深度

方法1&#xff1a;深度优先遍历 //给定一个二叉树 root &#xff0c;返回其最大深度。 // // 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 // // // // 示例 1&#xff1a; // // // // // // //输入&#xff1a;root [3,9,20,null,null,15,7…

16:00面试,16:06就出来了,问的问题过于变态了。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到2月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…

【茶话数据结构】查找最短路径——Dijkstra算法详解(保姆式详细图解,步步紧逼,保你学会)

&#x1f4af; 博客内容&#xff1a;【茶话数据结构】查找最短路径——Dijkstra算法详解 &#x1f600; 作  者&#xff1a;陈大大陈 &#x1f989;所属专栏&#xff1a;数据结构笔记 &#x1f680; 个人简介&#xff1a;一个正在努力学技术的准前端&#xff0c;专注基础和实…

数据结构之顺序表及其实现!

目录 ​编辑 1. 顺序表的概念及结构 2. 接口的实现 2.1 顺序表的初始化 2.2 检查顺序表容量是否已满 2.3 顺序表的尾插 ​编辑 2.4 顺序表的尾删 2.5 顺序表的头插 2.6 顺序表的头删 2.7 顺序表在pos位置插入 2.8 顺序表在pos位置删除 2.9 顺序表的查找 2.10 顺…