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,vk−1,max{Du,kk−1,Dk,vk−1}}
代码如下
#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)
题意 给出一个图,图中的边表示从点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}^…...
Redis概述
目录 Redis - 概述 使用场景 如何安装 Window 下安装 Linux 下安装 docker直接进行安装 下载Redis镜像 Redis启动检查常用命令 Redis - 概述 redis是一款高性能的开源NOSQL系列的非关系型数据库,Redis是用C语言开发的一个开源的高键值对(key value)数据库,官方提供测试…...
MsrayPlus多功能搜索引擎采集软件
MsrayPlus多功能搜索引擎采集软件 摘要: 本文介绍了一款多功能搜索引擎软件-MsrayPlus,该软件能够根据关键词从搜索引擎中检索相关数据,并提供搜索引擎任务、爬虫引擎任务和联系信息采集三大功能。我们将分析该软件在不同领域的应用…...
机器学习之概率论
最近,在了解机器学习相关的数学知识,包括线性代数和概率论的知识,今天,回顾了概率论的知识,贴上几张其他博客的关于概率论的图片,记录学习过程。...
【深度学习 | 数据可视化】 视觉展示分类边界: Perceptron模型可视化iris数据集的决策边界
🤵♂️ 个人主页: AI_magician 📡主页地址: 作者简介:CSDN内容合伙人,全栈领域优质创作者。 👨💻景愿:旨在于能和更多的热爱计算机的伙伴一起成长!!&…...
【计算机视觉】相机基本知识(还在更新)
1.面阵工业相机与线阵工业相机 1.1 基本概念区别 面阵相机则主要采用的连续的、面状扫描光线来实现产品的检测; 线阵相机即利用单束扫描光来进行物体扫描的工作的。 1.2 优缺点 (1)面阵CCD工业相机: 优点:应用面…...
C++ (友元)(类嵌套时,成员函数以及类声明定义的顺序)小demo
#include<iostream> using namespace std; class Building; //1.因为Goodgay类需要声明Building类变量, //所以Building类必须Goodgay类之前声明(前向声明); class GoodGay { public:GoodGay();void visit(); private:Build…...
前端实习第五周周记
前言 每一天做了什么还是要记录一下,不然过两天后就会发现,慢慢遗忘自己的收获与做过的东西。 这周做的是医学检验系统的样本库部分。由于是公司的代码所以不能交代具体,那么久聊一下每天具体做了些什么以及我的一些收获。 周一 周一上午…...
【图论】Floyd算法
一.简介 Floyd算法,也称为Floyd-Warshall算法,是一种用于解决所有节点对最短路径问题的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。 Floyd算法的基本思想是通过中间节点逐步优化路径长度。它使用一个二维数组来存储任意两…...
ceph数据分布
ceph的存储是无主结构,数据分布依赖client来计算,有两个条主要路径。 1、数据到PG 2、PG 到OSD 有两个假设: 第一,pg的数量稳定,可以认为保持不变; 第二, OSD的数量可以增减,OSD的…...
mysql的两张表left join 进行关联后,索引进行优化案例
一 mysql的案例 1.1 不加索引情况 1.表1没加索引 2.表2没加索引 3.查看索引 1.2 添加索引 1.表1添加索引 2.表2添加索引 3.查看...
2018年3月全国计算机等级考试真题(语言二级C)
2018年3月全国计算机等级考试真题(语言二级C) 第1题 设有定义:char s[81];int i0;以下不能将一行带有空格的字符串正确读入的语句或语句组是 A. while((s[i]getchar())!\n);s[i]\0; B. scanf("%s",s); C.…...
java.util.Timer简介以及简单使用示例
一、简介 定时器(Timer)是一个工具类,用于安排任务(java.util.TimerTask)在指定时间后执行或以指定的时间间隔重复执行。它可以用于执行定时任务、定时调度和时间延迟等操作。 定时器(Timer)可以…...
C语言笔试训练【第12天】
文章目录 1、请阅读以下程序,其运行结果是( )2、假设编译器规定 int 和 short 类型长度分别为32位和16位,若有下列C语言语句,则 y 的机器数为( )3、下列程序的输出结果是什么( &…...
外网连接局域网的几种方式?快解析内网穿透安全便利吗?
外网连接局域网是一项网络连接中的关键技术,它能够让远程用户通过互联网访问内部局域网中的资源和服务。外网连接局域网为企业提供了更大的灵活性和便捷性,但也需要严格的安全措施来防止未经授权的访问。 外网连接局域网的几种方式 在将外网连接到局域…...
基于互斥锁的生产者消费者模型
文章目录 生产者消费者 定义代码实现 / 思路完整代码执行逻辑 / 思路 局部具体分析model.ccfunc(消费者线程) 执行结果 生产者消费者 定义 生产者消费者模型 是一种常用的 并发编程模型 ,用于解决多线程或多进程环境下的协作问题。该模型包含…...
USB隔离器电路分析,SA8338矽塔sytatek电机驱动,源特科技VPS8701,开关电源,电源 大师
一、 USB隔离器电路分析 进行usb隔离可以使用USB隔离模块 ADUM3160 ADUM4160 注意:B0505S 最大带载0.16A,副边需要带载能力需要改变方案 比如移动硬盘至少需要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并发服务器模型
作业: 1. 多线程中的newfd,能否修改成全局,不行,为什么? 2. 多线程中分支线程的newfd能否不另存,直接用指针间接访问主线程中的newfd,不行,为什么? 多线程并发服务器模型原代码&…...
认识负载均衡||WEBSHELL
目录 一、负载均衡 1.nginx负载均衡算法 2.nginx反向代理-负载均衡 二、webshell 1.构造不含数字和字母的webshell 2.如何绕过 一、负载均衡 1.nginx负载均衡算法 (1)轮询(默认)每个请求按时间顺序逐一分配到不同的后端服务&…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
