这两题有着相似的地方。都只求所有路径中的最长边的最小值。
不同之处在于Frogger求的是固定起点和终点，而Highways是所有路径。
所以Highways可以用最小生成树来求。而Frogger中起点和终点可以当成一组特值，所以可以考虑先求任意两点间的最小最长边，可以由此想到Warshell-Floyd算法，但是需要修改。当路径经过k时，分别考虑[i, k] 和 [k, j] 的最小最长边，故d[i][j] = min(d[i][j], max(d[i][k], d[k][j])。这样就考虑了所有路径的情况。
Highways我被样例骗了，以为两点之间的是一条双向边，然而，是两条单向边。
版权声明：本文为u012810326原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。