UVa 10986 - WinDaLex/Programming GitHub Wiki

Lift Hopping

from Volume 7. Graph Algorithms and Implementation Techniques

Description

几个服务器间发信息。输入从某个服务器发信息到某个服务器需要的时间，和信息出发点的目的地。输出从某台服务器发送到另外某台服务器需要的最短时间。

Solution

明显可以构成有向图。构图后用Dijkstra求单源最短路径即可。由于边数远小于点数的平方，属于稀疏图，因此最好用单调队列优化的Dijkstra来做。