当前位置: 首页 > 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之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...