当前位置: 首页 > 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;每个请求按时间顺序逐一分配到不同的后端服务&…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)

引言 在嵌入式系统中&#xff0c;用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例&#xff0c;介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单&#xff0c;执行相应操作&#xff0c;并提供平滑的滚动动画效果。 本文设计了一个…...

【记录坑点问题】IDEA运行:maven-resources-production:XX: OOM: Java heap space

问题&#xff1a;IDEA出现maven-resources-production:operation-service: java.lang.OutOfMemoryError: Java heap space 解决方案&#xff1a;将编译的堆内存增加一点 位置&#xff1a;设置setting-》构建菜单build-》编译器Complier...

数据挖掘是什么?数据挖掘技术有哪些?

目录 一、数据挖掘是什么 二、常见的数据挖掘技术 1. 关联规则挖掘 2. 分类算法 3. 聚类分析 4. 回归分析 三、数据挖掘的应用领域 1. 商业领域 2. 医疗领域 3. 金融领域 4. 其他领域 四、数据挖掘面临的挑战和未来趋势 1. 面临的挑战 2. 未来趋势 五、总结 数据…...