uva 10801 - Lift Hopping

<a target="_blank" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;page=show_problem&amp;category=24&amp;problem=1742&amp;mosmsg=Submission+received+with+ID+10636251">点击打开链接uva 10801</a>

思路：最短路+Dijkstra

分析：

         1 有n个电梯，电梯可以到达的层数是一定的，那么我们就把楼层看成是图上的点，那么我们就可以得到的哪些点是有连通的。

         2 又由于有多个电梯，所以x-&gt;y可能有多种方式，所以这就类似于重边问题那么我们要选择边权值最小的最为最后的边权值。

         3 接下来图建好以后就是考虑怎么Dijkstra，由于要交换乘坐电梯，那么我们就自然的想到了图论中的换边（松弛步），那么我们就把换乘电梯看成是在换边，就是说只要做松弛步就是在换成电梯，那么这个时候就要加上等电梯的时间60s。

         4 这里有个地方就是由于源点是会做松弛步的，但是源点是不用加上60s的，所以最后输出的时候要特判一下。如果k为0，直接输出0；如果k部位0，那么最后的输出要减去60.

代码：