大衞的筆記

QUESTION! Win10 無法更新安裝，並顯示 virutalbox 需要解除安裝，但電腦沒有此文件

能夠針對有、無權重的有向圖做出單點全源最短路徑演算法。

• 單點全源：從 A 點到任意邊的最短距離
  時間複雜度為 \(O((E+V)log V)\)，E 為邊、V 為頂點

在一個城市中，每一條道路都必須要收過路費。
其中會給你一個數值 p，你從出發點到終點不可以花超過 p 費用，並且在符合前面條件下，會產生 toll
toll: 在你走的路徑中，花費最多一次的過路費。
請你找出最大的 toll 是多少。

題目連結

Patricia 是個傑出的軟體工程師，但她有一些怪癖，喜歡偶數的事物，例如:喜歡買偶數張電影票、一天吃兩餐 or 四餐…等。
在 Patricia 所住的城市需要收過路費，Patricia 想從 1 到 x 點，她希望他可以被收偶數次的過路費，並且花費最少，你則必須輸出花費最小的數值為多少。

題目連結

生物學家讓西洋棋的騎士更跟其他棋子進行雜交，因此現在產生了一種棋子叫做怪異騎士，怪異騎士總共有三種型態，依序是普通騎士、變異騎士、變異士兵。

• 普通騎士與一般騎士走法相同
• 變異騎士則是比一般騎士的長度再多一格
• 變異士兵走法與一般士兵相同，但變異士兵在走最後一步時可以走一格對角線

現在給你一個棋盤 \(N*N\) 再給你怪異騎士的初始位置，請你讓怪異騎士走到終點。
請給出最小步數走法

題目連結

這個國家的人民們都是西洋棋騎士，因此他們只能夠走西洋棋棋法；土地也跟西洋棋的棋盤相似。
有天，他們的土地上出現了一個怪物，這個怪物很特別

• 長年都在睡覺
• 只要有一個騎士經過，怪物則會醒來，但不會吃掉他
• 接下來只要有其他騎士走過都會被吃掉

由於四位騎士必須聚在一起討論會議，因此他們要找一個沒有怪物的格子開會。
保險起見，當有一個騎士在行走時，其他騎士不會行走，以確保安全。
想知道，這些騎士們聚集在土地上的哪一個格子會讓騎士們行走距離最小，輸出最小行走距離。

題目連結

給你一個西洋棋盤，給你 A、B、C 座標，請透過上下左右、對角線的方式從 A 走到 B 並繞開 C，最短距離為多少？

題目連結

中文連結，她講得太好了
題目連結

Brett 現在人在 Calgary 他想要透過飛機到 Fredericton，他想要走最省錢的方式抵達，他可以忍受 x 次轉機
請告訴 Brett 他最多忍受幾次轉機，最省錢抵達 Fredericton 的成本是多少

題目連結

有一台神奇的車子，稱呼為 magic car

• 發動跟結束都需要耗費能量
• 中間距離所使用的能量是這樣計算的：\(max(每一條街最大的能量) - min(每一條街最大的能量\)
  現在這台車子要從 A 到 B，會經過許多條路，請你告訴我走最省油的路徑抵達 B 點時，會花多少能量

題目連結