最短路--floyed(奶牛跨栏)
奶牛的训练场中有 N (1 ≤ N ≤ 300) 个站台,分别标记为1..N。所有站台之间有M (1 ≤ M ≤ 25,000)条单向路径,第i条路经是从站台Si开始,到站台Ei,其中最高的栏的高度为Hi (1 ≤ Hi ≤ 1,000,000)。无论如何跑,奶牛们都要跨栏。
奶牛们有 T (1 ≤ T ≤ 40,000) 个训练任务要完成。第 i 个任务包含两个数字 Ai 和 Bi (1 ≤ Ai ≤ N; 1 ≤ Bi ≤ N),表示奶牛必须从站台Ai跑到站台Bi,可以路过别的站台。奶牛们想找一条路径从站台Ai到站台Bi,使路径上最高的栏的高度最小。
你的任务就是写一个程序,计算出路径上最高的栏的高度的最小值。
首先注意:不一定要是走最短路 因此这道题的目的是 通过floyed,找出可能的路径中,栅栏的长度尽量小的,
于是就有了
tu[i][j]=min(tu[i][j],max(tu[i][k],tu[k][j]));
(max(tu[i][k],tu[k][j])可以找出可能的路径中的最大值) (min则用来找出最大值的最小,即最高的栏的高度的最小值)