10801: Lift Hopping ★★★☆☆ 題組：Problem Set Archive with Online Judge

Presentation on theme: "10801: Lift Hopping ★★★☆☆ 題組：Problem Set Archive with Online Judge"— Presentation transcript:

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

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

4 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樓時結束)。

5 (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)

6 (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]即為所求。

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

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

9 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

10 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

11 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 <5000 Push：50(已存在) time 10 20 30 40 50 … = 100 1000 300 400 5000 200 500 3000

12 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 <1000 Push：20 time 10 20 30 40 50 … = 100 1000 300 400 5000 200 500 3000 省略(無更新) Pop：40 Pop：50

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

14 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

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

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