10801: Lift Hopping ★★★☆☆ 題組：Problem Set Archive with Online Judge 解題者：丘珮珊 解題日期：2015年5月14日 題意：一摩天大樓高度不超過100 層樓(編號0~99) ，內有n(1~5)台電梯。每台電梯上下一層樓的速度T(1~100秒/樓)都不同，且各電梯只停靠特定樓層。 若要換搭另一台電梯，則兩電梯都要停在同一樓，並須等待60秒。 求從0樓搭電梯到k樓所需的最時間(秒)，不可能到達則輸出IMPOSSIBLE。

題意範例： 2 30 2台電梯，目的k為30樓 10 5 電梯1速度為10秒/樓，電梯2速度為5秒/樓 0 1 3 13 15 20 99 電梯1停靠的樓層 4 13 15 19 20 30 電梯2停靠的樓層 =>275 (130+60+85) 電梯1，0~13樓，13*10=130秒 換電梯2，60秒 電梯2，13~30樓，17*5=85秒 3 50 3台電梯，目的k為50樓 10 50 100 速度分別為10秒/樓、50秒/樓、 100秒/樓 0 10 30 40 電梯1停靠的樓層 0 20 30 電梯2停靠的樓層 0 20 50 電梯3停靠的樓層 =>3920 (300+60+500+60+3000) 電梯1，0~30樓，30*10=300秒，換電梯等60秒 電梯2，30~20樓，10*50=500秒，換電梯等60秒 電梯3，20~50樓，30*100=3000

解法： 先計算不換電梯時各層樓間移動所需的最短時間(計算權重)，最後再計算換電梯時0樓到各樓所需的最短時間(尋找最短路徑)。 1 解法： 先計算不換電梯時各層樓間移動所需的最短時間(計算權重)，最後再計算換電梯時0樓到各樓所需的最短時間(尋找最短路徑)。 1.不換電梯： (計算權重、找相鄰的點) 二維陣列time[i][j]：i到j樓所需的最短時間，初始值為無限大。 每當輸入電梯停靠的樓層時，更新time： 有一電梯的速度為t秒/樓，以此電梯可停靠的各樓層i當作起始點，若到達其他可停靠樓層j的時間比time所存的短 ( | i-j |*t < time[i][j] )，則更新time的值。 20 30

2.換電梯： (尋找最短路徑) (1)Dijkstra演算法： 一維陣列mint[i]：0到i樓所需的最短時間，初始值為不換電梯的最短時間(time[0][i])。 Queue Q：紀錄已是最小值的點，初始值為0樓。 找到mint[]的最小值mint[i]，且i不在Q中，將i push入Q。 以i為中繼點重新計算mint： j=可停靠的樓層，若0到i樓+換電梯60秒+i到j樓，小於目前0到j樓的時間(mint[i]+60+time[i][j]< mint[j])，則更新mint[j]。 步驟重複步驟(1)、(2)直到Q內含有所有可停靠的樓層(或Q含有k樓時結束)。

(2)Bellman-Ford演算法： 一維陣列mint[i]：0到i樓所需的最短時間，初始值為不換電梯的最短時間(time[0][i])。 以i為中繼點重新計算mint： i、j=i可到達的點，窮舉所有(i,j)，使mint[i]+60+time[i][j]< mint[j]，更新mint[j]。 重複步驟(1)V(# of vertex)-1次。 時間複雜度：O(VE)

(3)SPFA(Shortest Path Faster Algorithm)演算法： Bellman-Ford演算法優化，減少步驟(1)重複的次數。 一維陣列mint[i]：0到i樓所需的最短時間，初始值為不換電梯的最短時間(time[0][i])。 queue Q：欲成為中繼點更新mint的樓層，初始值為0可到達的樓層(time[0][i]!=無限大)。 pop Q得i。 以i為中繼點重新計算mint： j=可停靠的樓層，若mint[i]+60+time[i][j]< mint[j]，更新mint[j]。 當mint[j]的值更改時，代表以j為中繼點可能出現更短的路徑，因此將j push入Q(若j在Q中則不用)。 重複步驟(1)~(3)直到Q內為空。 3.輸出： 若mint[k]=無限大則輸出IMPOSSIBLE，否則mint[k]即為所求。

| i-j |*t < time[i][j] 解法範例： 3 50 3台電梯，目的k為50樓 10 50 100 速度分別為10秒/樓、50秒/樓、 100秒/樓 0 10 30 40 電梯1停靠的樓層 0 20 30 電梯2停靠的樓層 0 20 50 電梯3停靠的樓層 1.不換電梯： (計算權重) | i-j |*t < time[i][j] time 10 20 30 40 50 … = 100 1000 300 400 5000 200 500 3000

300 40 10 400 100 1000 200 20 5000 3000 300 50 30 500

2.換電梯： (尋找最短路徑、找相鄰的點) SPFA演算法 mint[i]+60+time[i][j]< mint[j] Q 10 20 30 40 50 Push：10、20、30、40、50 10 20 30 40 50 100 1000 300 400 5000 mint 初始化 time 10 20 30 40 50 … = 100 1000 300 400 5000 200 500 3000

mint[i]+60+time[i][j]< mint[j] Q 20 30 40 50 Pop：10 10 20 30 40 50 100 1000 300 400 5000 mint time 10 20 30 40 50 … = 100 1000 300 400 5000 200 500 3000

mint[i]+60+time[i][j]< mint[j] Q 30 40 50 Pop：20 10 20 30 40 50 100 1000 300 400 4060 mint 1000+60+3000<5000 Push：50(已存在) time 10 20 30 40 50 … = 100 1000 300 400 5000 200 500 3000

mint[i]+60+time[i][j]< mint[j] Q 40 50 20 Pop：30 10 20 30 40 50 100 860 300 400 4060 mint 300+60+500<1000 Push：20 time 10 20 30 40 50 … = 100 1000 300 400 5000 200 500 3000 省略(無更新) Pop：40 Pop：50

mint[i]+60+time[i][j]< mint[j] Q 50 Pop：20 10 20 30 40 50 100 860 300 400 3920 mint 860+60+3000<4060 Push：50 time 10 20 30 40 50 … = 100 1000 300 400 5000 200 500 3000

mint[i]+60+time[i][j]< mint[j] Q Pop：50 10 20 30 40 50 100 860 300 400 3920 mint 結束 time 10 20 30 40 50 … = 100 1000 300 400 5000 200 500 3000

300 40 10 400 100 1000 200 20 換電梯+60 5000 3000 300 50 換電梯+60 30 500

討論： (1)一開始看到題目知道要找最短路徑，但卻不知該如何下手，後來想到最短路徑問題與圖有很大的關連，所以找出圖的特徵後，就能比較容易解題。例如本題：找出相鄰的點、各邊的權重。