算法竞赛入门经典|例题11-5 噪音恐惧症（Audiophobia, UVa10048）
欢迎访问我的Uva题解目录 https://blog.csdn.net/richenyunqi/article/details/81149109
题目描述 
文章图片
题意解析 输入一个C个点S条边（C≤100，S≤1000）的无向带权图，边权表示该路径上的噪声值。当噪声值太大时，耳膜可能会受到伤害，所以当你从某点去往另一个点时，总是希望路上经过的最大噪声值最小。输入一些询问，每次询问两个点，输出这两点间最大噪声值。
算法设计 参照《算法竞赛入门经典（第2版）》中的提示：
【算法竞赛入门经典|例题11-5 噪音恐惧症（Audiophobia, UVa10048）】本题的做法十分简单：直接用floyd算法，但是要把加法改成min，min改成max。为什么可以这样做呢？不管是floyd算法还是dijkstra算法，都是基于这样一个事实：对于任意一条至少包含两条边的路径 i ? > j i-> j i?>j，一定存在一个中间点k，使得 i ? > j i-> j i?>j的总长度等于 i ? > k i-> k i?>k与 k ? > j k-> j k?>j的长度之和。对于不同的点k， i ? > k i-> k i?>k和 k ? > j k-> j k?>j的长度之和可能不同，最后还需要取一个最小值才是 i ? > j i-> j i?>j的最短路径。把刚才的推理中“之和”与“取最小值”换成“取最小值”和“取最大值”，推理仍然适用。C++代码
#include
using namespace std;
int C,S,Q,graph[105][105];
const int INF=0x3fffffff;
int main(){
for(int ii=1;
scanf("%d%d%d",&C,&S,&Q)&&C!=0;
++ii){
printf("%sCase #%d\n",ii>1?"\n":"",ii);
for(int i=0;
i 推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- typeScript入门基础介绍
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）