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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月08日 06时32分03秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
matlab数学规划模型,数学规划模型
2019-04-21
视频提取音频php,如何提取视频中的音频,从视频文件中提取出音频输出成MP3格式...
2019-04-21
diy.php添加验证码,织梦dedecms自定义表单中加入验证码
2019-04-21
c语言 无错 但只运行一半,求哈夫曼编码时程序运行到一半就终止了,编译无错...
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
es审计日志_elasticsearch 事务日志translog
2019-04-21
dw1510_超低温种子储存柜
2019-04-21
广州刷脸支付骗局_刷脸支付是骗局?那可能你还不了解刷脸支付
2019-04-21
java 远程调试 端口_JAVA远程调试
2019-04-21