POJ 3255 Roadblocks 次短路

Input

Output

Sample Input

Sample Output

每個節點有2種狀态。 0 代表最短路， 1代表次短路。

通過djkstra的思路， 當某個點的狀态發生改變，那麼就将該點進行入隊。每次從隊列裡面找出距離最短的進行更新其他節點。每個狀态隻會出隊一次。

是以若求出的路徑小于該點已經求得的最短路， 那麼讓次短路等于之前的最短路， 最短路等于新求出的路徑。 這時候有2個節點狀态改變是以2個節點入隊。