網頁

2014年4月3日 星期四

UVa 10801 Lift Hopping

題意:
    有n個電梯(1<=n<=5),每個電梯移動一層樓的時間不一樣,第i個電梯每層樓的移動時間以T[i]表示,而每個電梯能到達的樓層也不一樣,如果兩個電梯都能到達x樓,則能在x樓換另一台電梯搭乘,但轉換的時間為60秒。今天起點在第0樓,給定第k樓為要前往的樓層,問最短的時間?
想法:
    先以Weight[i][j]表示在'不轉換'電梯的情況下,i樓到j樓所需的最短時間,這個部份可以在輸入測資的過程中一起完成。然後再考慮轉換電梯的情況,以Dis[i]表示到達i樓的時間,用SPFA演算法,每次queue的時候就判斷 if (Dis[now] + Weight[now][nxt] + 60 < Dis[nxt]) 來不斷更新Dis[nxt]的值。