题目描述
有一个C个点S条边(C≤100,S≤1000)的无向带权图,边权表示该路径上的噪声值。当噪声值太大时,耳膜可能会受到伤害,所以当你从某点去往另一个点时,总是希望路上经过的最大噪声值最小。输入一些询问,每次询问两个点,输出这两个点之间噪声值最小的路径上的最大噪声值。
输入描述
第一行两个整数C和S。
下面S行每行3个整数Vx,Vy,W,分别表示边的两个端点和权值,顶点从0到C-1编号。W不超过10000
第S+2行一个整数T,表示询问次数,T≤C(C-1)。
下面T行每行2个整数Vx,Vy,表示要询问的两个点。
输出描述
共T行,每行一个整数表示该次询问的答案。
样例输入
7 9
0 1 50
0 2 60
1 3 120
1 4 90
2 5 50
3 5 80
3 6 70
4 6 40
5 6 140
1
0 6
样例输出
80
提示
采用Floyd算法,把松弛时的求和改为求最大值即可