UVA 10048 Audiophobia (Floyd变形)
发布日期:2022-02-17 09:51:12 浏览次数:8 分类:技术文章

本文共 1526 字,大约阅读时间需要 5 分钟。

UVA 10048 Audiophobia (Floyd变形)

题意

输入一个C个点S条边(C≤100,S≤1000)的无向带权图,边权表示该路径上的噪声值。

当噪声值太大时,耳膜可能会受到伤害,所以当你从某点去往另一个点时,总是希望路上经
过的最大噪声值最小。输入一些询问,每次询问两个点,输出这两点间最大噪声值最小的路
路径。

思路

直接用Floyd算法,但是需要做一些改动:

  • 加法改成algorithm中的min();

  • min()改成max();

代码

#include 
#include
#include
#include
const int N = 105;const int INF = 0x3f3f3f;using namespace std;int d[N][N];int c, s, q;int a, b, x;int cas = 0;void init(){
for (int i = 1; i <= c; i++) {
for (int j = 1; j <= c; j++) {
d[i][j] = INF; } } for (int i = 1; i <= s; i++) {
scanf("%d%d%d", &a, &b, &x); d[a][b] = d[b][a] = x; }}void Floyd(){
for (int k = 1; k <= c; k++) {
for (int i = 1; i <= c; i++) {
for (int j = 1; j <= c; j++) {
d[i][j] = min(d[i][j], max(d[i][k], d[k][j])); //设d [ i ][ j ]表示 i 到 j 的最大噪音的最小值。 那么d [ i ][ j ] = min( d[ i ][ j ] ,max( d [ i ][ k ] , d [ k ][ j ]) ); } } }}int main(){
while(scanf("%d%d%d", &c, &s, &q)&&c&&s&&q) {
cas++; init(); Floyd(); if (cas > 1) printf("\n"); printf("Case #%d\n", cas); for (int i = 0; i < q; i++) {
scanf("%d%d", &a, &b); if (d[a][b] == INF) {
printf("no path\n"); } else {
printf("%d\n", d[a][b]); } } } return 0;}

转载地址:https://blog.csdn.net/qq_43826794/article/details/102488963 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:HDU2896 病毒入侵
下一篇:Codeforces Round #594 (Div. 2) B. Grow The Tree

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月08日 06时32分03秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

matlab数学规划模型,数学规划模型 2019-04-21
视频提取音频php,如何提取视频中的音频,从视频文件中提取出音频输出成MP3格式... 2019-04-21
diy.php添加验证码,织梦dedecms自定义表单中加入验证码 2019-04-21
在php脚本中 通过可以获取,在PHP中,可以使用Unix时间戳获取精确的脚本执行时间。... 2019-04-21
s2-045 php exp,S2-045-EXP.py --Struts2任意代码执行漏洞 (S2-045,CVE-2017-5638) 2019-04-21
linux sdk 窗口句柄,Venus: 针对Linux平台上,对常用的系统API进行面向对象的封装SDK。... 2019-04-21
c语言程序设计 科学出版社习题答案,C语言程序设计(科学出版社)第4章 课后习题参考答案.doc... 2019-04-21
c语言 无错 但只运行一半,求哈夫曼编码时程序运行到一半就终止了,编译无错... 2019-04-21
deepin linux 2014安装,2014.2版本的Deepin虚拟机安装浅谈(就是深度Linux) 2019-04-21
android 限速工具,Android下载器之限速篇 2019-04-21
html刷新ajax实现原理,AJAX的原理—如何做到异步和局部刷新 2019-04-21
html中列表菜单加文字请选择,html中下拉菜单 2019-04-21
读书郎平板中android,读书郎学生平板电脑怎么用 使用方法详解【图文】 2019-04-21
html5 调用摄像头 支持IE,JS调用本地摄像头拍照(兼容各大浏览器及IE8+) 2019-04-21
rust和gta5哪个吃配置_盘点4款Steam“自由度”很高的游戏,GTA5众所周知,目前最热门... 2019-04-21
es审计日志_elasticsearch 事务日志translog 2019-04-21
dw1510_超低温种子储存柜 2019-04-21
文件未找到mathpage.wll_解决MathPage.wll文件找不到的问题(找了好久的良心之作)... 2019-04-21
广州刷脸支付骗局_刷脸支付是骗局?那可能你还不了解刷脸支付 2019-04-21
java 远程调试 端口_JAVA远程调试 2019-04-21