描述
Asterix 和 Obelix 在戰爭勝利後，基於一些因素，Asterix 決定要在回家的路上，找個城市宴請 Obelix，考慮到 Obelix 的食量大（看看那體型），為保險起見，Asterix 決定在路過的城市中，選花費最高的城市舉辦宴會，除此之外，城市間的道路都會收取數額不等的過路費。給定出發城市 \(c_s\) 和目的城市 \(c_e\)，求 Asterix 花費的最小金額。
思路
第一層
每當 Asterix 要前往下一個城市時，選擇的道路和抵達的城市都會影響到花費，道路的選擇想當然耳，是花費越低的越好，但是選花費最低的道路，卻有可能導致抵達的城市不是 Asterix 該去的，怎麼說呢？
假設 Asterix 可以去甲城市或乙城市（兩者都不是目的城市），路費分別為 \(n\) 和 \(m\)，宴會費用為 \(l\) 和 \(s\)，並且 \(n < m < s < l\)，若挑花費較低的道路，Asterix 會抵達宴會成本較高的甲城市，那麼問題來了：
- 如果甲城市的宴會費用是目前所有路過城市中最高的，那麼 Asterix 只能選擇在甲城市舉辦宴會，在此情況下，之前的路線選擇還會是最優的嗎？
答案是不一定，這告訴我們不理會宴會費用，只考慮最短路徑是不現實的，既然要思考的這麼多，那暴力解試試？當然，試試就逝世，直接暴力解會 TLE，這是因為只要給定的圖稍大，計算時間會毫不意外地變很長，並且對於同一張圖，會有許多不同出發城市和目的城市的查詢，拿個 TLE 認證並不冤枉。
第二層
題目的敘述會誘導我們以路線的角度思考，但只要從路線的角度思考，就會遇到上面提到的問題，很容易讓人想要躺平放棄，既然這個方向令人頭禿，我們不妨換個思路。
對於一個城市，只要能跟出發城市和目的城市「連通」，必然存在一條花費最小的路徑，這看起來像是廢話，但如果該城市是用來舉辦宴會的城市呢？此刻問題被轉換為求出發城市到該城市和該城市到目的城市的最短路徑問題，要在一個城市舉辦宴會，必須要保證所有經過城市的宴會費用都不比該城市高，此為重要的約束條件，是強調連通二字的原因。按此思路，我們只要分別對所有城市（包含出發城市和目的城市），求出發城市到該城市和該城市到目的城市的最短路徑長度（別忘了約束），並加上該城市的宴會費用，再從中找數值最低的即為答案。
以 \(cost(c_i)\) 表 \(c_i\) 城市舉辦宴會的費用，\(d(c_i, c_j)\) 表 \(c_i\) 城市到 \(c_j\) 城市且沿途城市的費用都不超過 \(cost(c_i)\) 的最短路徑的長度，則本題的答案可以由
\[ \begin{equation} \min_{c_n \in V}\; (d(c_n, c_s) + d(c_n, c_e) + cost(c_n)) \end{equation} \]
給出，其中 \(V\) 為所有城市構成的集合。
實作上有兩種方式，一是用需要 \(O((|E|+|V|)log|V|)\) 的 Dijkstra 演算法或需要 \(O(|E||V|)\) 的 Bellman-Ford 演算法，執行 \(C^{|V|}_2\) 次求得所有點間的最短路徑，再根據出發城市和目的城市進行每次 \(O(n)\) 的查詢，二是用需要 \(O(|V|^3)\) 的魔改 Floyd-Warshall 演算法，需要魔改之處為將宴會花費融入該動態規劃方法中，完成後，根據出發城市和目的城市進行每次 \(O(1)\) 查詢即可。
範例
1 | 4 4 2 |
將輸入繪成相應的地圖（圈中數字為城市編號，圈上數字為宴會費用，連線下數字為過路費）。
A. 先初始化用來儲存 \(d(c_i, c_j)\) 的陣列，若 \(c_i\) 和 \(c_j\) 相同，則為 \(0\)，若不同則為 \(\infty\)。
| \(c_i\) \ \(c_j\) | \(c_1\) | \(c_2\) | \(c_3\) | \(c_4\) |
| \(c_1\) | \(0\) | \(\infty\) | \(\infty\) | \(\infty\) |
| \(c_2\) | \(\infty\) | \(0\) | \(\infty\) | \(\infty\) |
| \(c_3\) | \(\infty\) | \(\infty\) | \(0\) | \(\infty\) |
| \(c_4\) | \(\infty\) | \(\infty\) | \(\infty\) | \(0\) |
B. 求 \(d(c_1, c_2)\)，構造滿足約束的圖（圖中城市的花費不高於 \(cost(c_1)\)），依單源最短路徑演算法可以得到 \(d(c_1, c_2) = 7\)。
C. 求 \(d(c_2, c_1)\)，構造滿足約束的圖，得到 \(d(c_2, c_1) = \infty\)。
D. 求 \(d(c_1, c_3)\)，構造滿足約束的圖，得到 \(d(c_1, c_3) = \infty\)。
E. 求 \(d(c_3, c_1)\)，構造滿足約束的圖，得到 \(d(c_3, c_1) = 5\)。
F. 求 \(d(c_1, c_4)\)，構造滿足約束的圖，得到 \(d(c_1, c_4) = \infty\)。
G. 求 \(d(c_4, c_1)\)，構造滿足約束的圖，得到 \(d(c_4, c_1) = 15\)。事實上不難發現當 \(cost(c_i) \neq cost(c_j)\) ，若 \(d(c_i, c_j) = \infty\) 則 \(d(c_j, c_i) \neq \infty\)，且反之亦然。
F. 依相同方法求 \(d(c_2, c_3)\)、\(d(c_3, c_2)\)、\(d(c_2, c_4)\)、\(d(c_4, c_2)\)、\(d(c_3, c_4)\) 和 \(d(c_4, c_3)\)，完成陣列。
| \(c_i\) \ \(c_j\) | \(c_1\) | \(c_2\) | \(c_3\) | \(c_4\) |
| \(c_1\) | \(0\) | \(7\) | \(\infty\) | \(\infty\) |
| \(c_2\) | \(\infty\) | \(0\) | \(\infty\) | \(\infty\) |
| \(c_3\) | \(5\) | \(12\) | \(0\) | \(6\) |
| \(c_4\) | \(15\) | \(8\) | \(\infty\) | \(0\) |
F. 求 \(c_1\) 到 \(c_4\) 的最少花費，依式 \((1)\) 有
\[ \begin{align*} &d(c_1, c_1) + d(c_1, c_4) + cost(c_1) = \infty \\ &d(c_2, c_1) + d(c_2, c_4) + cost(c_2) = \infty \\ &d(c_3, c_1) + d(c_3, c_4) + cost(c_3) = 19 \\ &d(c_4, c_1) + d(c_4, c_4) + cost(c_4) = 18 \end{align*} \]
可得答案為 \(\min(\infty, \infty, 19, 18) = 18\)。
H. 求 \(c_2\) 到 \(c_3\) 的最少花費，依式 \((1)\) 有
\[ \begin{align*} &d(c_1, c_2) + d(c_1, c_3) + cost(c_1) = \infty \\ &d(c_2, c_2) + d(c_2, c_3) + cost(c_2) = \infty \\ &d(c_3, c_2) + d(c_3, c_3) + cost(c_3) = 20 \\ &d(c_4, c_2) + d(c_4, c_3) + cost(c_4) = \infty \end{align*} \]
可得答案為 \(\min(\infty, \infty, 20, \infty) = 20\)。
結論
本題初看是最短路徑的問題，再看不是最短路徑的問題，最後看還是最短路徑的問題，需要解題者轉換看問題的視角，否則會陷在看起來不是最短路徑的窘境。
備註
- 「阿斯泰利克斯歷險記」－標題中人名的出處
- 題目中的起始城市和目的城市分別為 \(c_1\) 和 \(c_2\)，為避免混淆，文中以 \(c_s\) 和 \(c_e\) 代之。
- 文中的漸進符號指最壞狀況下的時間複雜度。
- 用魔改的 Floyd-Warshall 演算法需要運行兩次（第二次不用初始化），不過到底為什麼需要兩次呢？