P2185 公路通行税 题解

今天才看到一道水题，切了再说。

题目大意翻译过来非常简单：给定一个无向连通图，求出任意两点之间最短路的最大值。

考虑到这张图中每条边的边权都是 ，使用 Dijkstra。只要我们遍历每个点，做一次 Dijkstra 即可，但是在数据量较大的时候会 TLE。

考虑优化 Dijkstra，既然每条边的边权都是 ，不妨模拟一下此时 Dijkstra 的执行过程。我们可以发现，若我们对每个点都做一遍 bfs，那么当某个点第一次被搜到时，其距离即为最短路。很容易证明，因为边数越少，则越早被搜到，而此时最短路的长度就是边数。最后顺便取一个 max 即可。

注意多测。

Code:

写完这么多，真的有很多想说的啊——

毕竟周六就去省选了啊——

可能，也许高二就 A(way) F(rom) O(I) 了啊，毕竟在 js，高二真的很不占优势啊——

可是，我才高一啊……

强省弱市弱校，我连我怎么苟活到现在都不知道。

我想回家……

也许，一切的一切，终究还是证明了我没有 tla 的资本。不管怎么努力，还是感觉配不上心中的那个 TA 啊。人家是年级第一，可我是什么？分数差了 40+ 啊（虽然文理选科不同）……

可是我真的不想失去 TA 啊，TA 笑的样子多可爱啊~~不是嘛——

也许 TA 是第一个了解我的人吧，至少我的感觉是这样的。TA 是我第一个喜欢上的 girl 啊，真的是第一个……

@数学太爱我

（如果能看到的话）