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.

代碼：