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

UVa10048 Audiophobia(floyd)

题意

给出一个图,图中的边表示从点u到点v路径上的噪音。给出q个查询,问从u到v所经路径上的最小噪音

思路

在使用floyd计算点对之间的路径时, D u , v k = m i n { D u , v k − 1 , m a x { D u , k k − 1 , D k , v k − 1 } } D_{u, v}^k= min \{D_{u, v}^{k - 1}, max\{D_{u, k}^{k- 1}, D_{k, v}^{k - 1}\}\} Du,vk=min{Du,vk1,max{Du,kk1,Dk,vk1}}
代码如下

#include <bits/stdc++.h>using namespace std;#define _for(i, a, b) for(int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)const int N = 104;
const int INF = 1e9;int graph[N][N];void fastio()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
}int main()
{fastio();#ifndef ONLINE_JUDGEifstream fin("f:\\OJ\\uva_in.txt");streambuf* back = cin.rdbuf(fin.rdbuf());#endifint kase = 1;int c, s, q;while (cin >> c >> s >> q) {if (c == 0 && s == 0 && q == 0) {break;}if (kase > 1) {cout << endl;}cout << "Case #" << kase++ << endl;_for(i, 0, c) {_for (j, 0, c) {graph[i][j] = (i == j) ? 0 : INF;}}_for(i, 0, s) {int c1, c2, d;cin >> c1 >> c2 >> d;--c1;--c2;graph[c1][c2] = min(graph[c1][c2], d);graph[c2][c1] = graph[c1][c2];}_for(k, 0, c) {_for(i, 0, c) {_for(j, 0, c) {if (graph[i][k] != INF && graph[k][j] != INF) {graph[i][j] = min(graph[i][j], max(graph[i][k], graph[k][j]));}}}}_for(i, 0, q) {int c1, c2;cin >> c1 >> c2;--c1;--c2;int ans = graph[c1][c2];if (ans == INF) {cout << "no path" << endl;} else {cout << ans << endl;}}}#ifndef ONLINE_JUDGEcin.rdbuf(back);#endifreturn 0;
}

相关文章:

UVa10048 Audiophobia(floyd)

题意 给出一个图&#xff0c;图中的边表示从点u到点v路径上的噪音。给出q个查询&#xff0c;问从u到v所经路径上的最小噪音 思路 在使用floyd计算点对之间的路径时&#xff0c; D u , v k m i n { D u , v k − 1 , m a x { D u , k k − 1 , D k , v k − 1 } } D_{u, v}^…...

​Redis概述

目录 Redis - 概述 使用场景 如何安装 Window 下安装 Linux 下安装 docker直接进行安装 下载Redis镜像 Redis启动检查常用命令 Redis - 概述 redis是一款高性能的开源NOSQL系列的非关系型数据库,Redis是用C语言开发的一个开源的高键值对(key value)数据库,官方提供测试…...

MsrayPlus多功能搜索引擎采集软件

MsrayPlus多功能搜索引擎采集软件 摘要&#xff1a; 本文介绍了一款多功能搜索引擎软件-MsrayPlus&#xff0c;该软件能够根据关键词从搜索引擎中检索相关数据&#xff0c;并提供搜索引擎任务、爬虫引擎任务和联系信息采集三大功能。我们将分析该软件在不同领域的应用&#xf…...

机器学习之概率论

最近&#xff0c;在了解机器学习相关的数学知识&#xff0c;包括线性代数和概率论的知识&#xff0c;今天&#xff0c;回顾了概率论的知识&#xff0c;贴上几张其他博客的关于概率论的图片&#xff0c;记录学习过程。...

【深度学习 | 数据可视化】 视觉展示分类边界: Perceptron模型可视化iris数据集的决策边界

&#x1f935;‍♂️ 个人主页: AI_magician &#x1f4e1;主页地址&#xff1a; 作者简介&#xff1a;CSDN内容合伙人&#xff0c;全栈领域优质创作者。 &#x1f468;‍&#x1f4bb;景愿&#xff1a;旨在于能和更多的热爱计算机的伙伴一起成长&#xff01;&#xff01;&…...

【计算机视觉】相机基本知识(还在更新)

1.面阵工业相机与线阵工业相机 1.1 基本概念区别 面阵相机则主要采用的连续的、面状扫描光线来实现产品的检测&#xff1b; 线阵相机即利用单束扫描光来进行物体扫描的工作的。 1.2 优缺点 &#xff08;1&#xff09;面阵CCD工业相机&#xff1a; 优点&#xff1a;应用面…...

C++ (友元)(类嵌套时,成员函数以及类声明定义的顺序)小demo

#include<iostream> using namespace std; class Building; //1.因为Goodgay类需要声明Building类变量&#xff0c; //所以Building类必须Goodgay类之前声明&#xff08;前向声明&#xff09;&#xff1b; class GoodGay { public:GoodGay();void visit(); private:Build…...

前端实习第五周周记

前言 每一天做了什么还是要记录一下&#xff0c;不然过两天后就会发现&#xff0c;慢慢遗忘自己的收获与做过的东西。 这周做的是医学检验系统的样本库部分。由于是公司的代码所以不能交代具体&#xff0c;那么久聊一下每天具体做了些什么以及我的一些收获。 周一 周一上午…...

【图论】Floyd算法

一.简介 Floyd算法&#xff0c;也称为Floyd-Warshall算法&#xff0c;是一种用于解决所有节点对最短路径问题的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。 Floyd算法的基本思想是通过中间节点逐步优化路径长度。它使用一个二维数组来存储任意两…...

ceph数据分布

ceph的存储是无主结构&#xff0c;数据分布依赖client来计算&#xff0c;有两个条主要路径。 1、数据到PG 2、PG 到OSD 有两个假设&#xff1a; 第一&#xff0c;pg的数量稳定&#xff0c;可以认为保持不变&#xff1b; 第二&#xff0c; OSD的数量可以增减&#xff0c;OSD的…...

mysql的两张表left join 进行关联后,索引进行优化案例

一 mysql的案例 1.1 不加索引情况 1.表1没加索引 2.表2没加索引 3.查看索引 1.2 添加索引 1.表1添加索引 2.表2添加索引 3.查看...

2018年3月全国计算机等级考试真题(语言二级C)

2018年3月全国计算机等级考试真题&#xff08;语言二级C&#xff09; 第1题 设有定义&#xff1a;char s[81]&#xff1b;int i0&#xff1b;以下不能将一行带有空格的字符串正确读入的语句或语句组是 A. while((s[i]getchar())!\n);s[i]\0; B. scanf("%s",s); C.…...

java.util.Timer简介以及简单使用示例

一、简介 定时器&#xff08;Timer&#xff09;是一个工具类&#xff0c;用于安排任务&#xff08;java.util.TimerTask&#xff09;在指定时间后执行或以指定的时间间隔重复执行。它可以用于执行定时任务、定时调度和时间延迟等操作。 定时器&#xff08;Timer&#xff09;可以…...

C语言笔试训练【第12天】

文章目录 1、请阅读以下程序&#xff0c;其运行结果是&#xff08; &#xff09;2、假设编译器规定 int 和 short 类型长度分别为32位和16位&#xff0c;若有下列C语言语句&#xff0c;则 y 的机器数为&#xff08; &#xff09;3、下列程序的输出结果是什么&#xff08; &…...

外网连接局域网的几种方式?快解析内网穿透安全便利吗?

外网连接局域网是一项网络连接中的关键技术&#xff0c;它能够让远程用户通过互联网访问内部局域网中的资源和服务。外网连接局域网为企业提供了更大的灵活性和便捷性&#xff0c;但也需要严格的安全措施来防止未经授权的访问。 外网连接局域网的几种方式 在将外网连接到局域…...

基于互斥锁的生产者消费者模型

文章目录 生产者消费者 定义代码实现 / 思路完整代码执行逻辑 / 思路 局部具体分析model.ccfunc&#xff08;消费者线程&#xff09; 执行结果 生产者消费者 定义 生产者消费者模型 是一种常用的 并发编程模型 &#xff0c;用于解决多线程或多进程环境下的协作问题。该模型包含…...

USB隔离器电路分析,SA8338矽塔sytatek电机驱动,源特科技VPS8701,开关电源,电源 大师

一、 USB隔离器电路分析 进行usb隔离可以使用USB隔离模块 ADUM3160 ADUM4160 注意&#xff1a;B0505S 最大带载0.16A&#xff0c;副边需要带载能力需要改变方案 比如移动硬盘至少需要0.5A 用充电宝、18650、设计5V1A输出电源 二、 1A隔离电压方案...

TPC-DS 测试是否支持 Glue Data Catalog?

在上一篇文章《在Hive/Spark上执行TPC-DS基准测试 (PARQUET格式)》中,我们详细介绍了具体的操作方法,当时的集群使用的是Hive Metastore,所有操作均可成功执行。当集群启用 Glue Data Catalog 时,在执行add_constraints.sql时会报错: Optimizing table date_dim (1/24).…...

网络编程(8.14)TCP并发服务器模型

作业&#xff1a; 1. 多线程中的newfd&#xff0c;能否修改成全局&#xff0c;不行&#xff0c;为什么&#xff1f; 2. 多线程中分支线程的newfd能否不另存&#xff0c;直接用指针间接访问主线程中的newfd,不行&#xff0c;为什么&#xff1f; 多线程并发服务器模型原代码&…...

认识负载均衡||WEBSHELL

目录 一、负载均衡 1.nginx负载均衡算法 2.nginx反向代理-负载均衡 二、webshell 1.构造不含数字和字母的webshell 2.如何绕过 一、负载均衡 1.nginx负载均衡算法 &#xff08;1&#xff09;轮询&#xff08;默认&#xff09;每个请求按时间顺序逐一分配到不同的后端服务&…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...