主題
題目連結：
題目意譯：
你被給定一個陣列 start，其中 start = [startX, startY] 代表你一開始在座標平面上的位置 (startX, startY)。你同時也被給定一個陣列 target，其中 target = [targetX, targetY] 代表著你的目標位置 (targetX, targetY)。
從一個位置 (x1, y1) 走到另一個位置 (x2, y2) 的成本為 |x2 - x1| + |y2 - y1|。
同時，平面上有一些特殊道路存在。你被給定一個二維陣列 specialRoads，其中 specialRoads[i] = [x1i, y1i, x2i, y2i, costi] 代表著第 i 條特殊道路可以從 (x1i, y1i) 單向地走到 (x2i, y2i) 且成本為 costi。你可以使用每一個特殊道路任意次。
回傳從 (startX, startY) 走到 (targetX, targetY) 所需的最小成本。
限制：
start.length == target.length == 2
1 ≦ startX ≦ targetX ≦ 10 ^ 5
1 ≦ startY ≦ targetY ≦ 10 ^ 5
1 ≦ specialRoads.length ≦ 200
specialRoads[i].length == 5
startX ≦ x1i, x2i ≦ targetX
startY ≦ y1i, y2i ≦ targetY
1 ≦ costi ≦ 10 ^ 5
範例測資：
範例 1：
輸入： start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
輸出： 5
解釋：
(1,1) 到 (1,2)，成本為 |1 - 1| + |2 - 1| = 1。
(1,2) 到 (3,3)。用的是 specialRoads[0]，成本為 2。
(3,3) 到 (3,4)，成本為 |2 - 3| + |4 - 3| = 1。
(3,4) 到 (4,5)。用的是 specialRoads[1]，成本為 1。
所以總成本為 1 + 2 + 1 + 1 = 5。
範例 2：
輸入： start = [3,2], target = [5,7], specialRoads = [[5,7,3,2,1],[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
輸出： 7
解釋：
最佳策略是不要使用任何特殊道路，直接從開始位置走到目標位置即可，其成本為 |5 - 3| + |7 - 2| = 7。
注意到 specialRoads[0] 是從 (5,7) 單向地到 (3,2)。
範例 3：
輸入： start = [1,1], target = [10,4], specialRoads = [[4,2,1,1,3],[1,2,7,4,4],[10,3,6,1,2],[6,1,1,2,3]]
輸出： 8
解釋：
(1,1) 到 (1,2)，成本為 |1 - 1| + |2 - 1| = 1。
(1,2) 到 (7,4)。用的是 specialRoads[1]，成本為 4。
(7,4) 到 (10,4)，成本為 |10 - 7| + |4 - 4| = 3。
解題思維：
把 specialRoads 中的點加上 start 和 target 全部混在一起，並建立一個有權重的鄰接矩陣 c（Adjacency Matrix，參見這題）。其中 c[i][j] 代表著點 i 直接地或是 (i, j) 存在於 specialRoads 走到點 j 的成本（取最小者）。
接著只需要跑一個最短路徑演算法即可，例如戴克斯特拉演算法（Dijkstra's Algorithm，參見維基的說明）甚至是 Floyd-Warshall 演算法（參見這題的說明）來算出 start 走到 target 的最短距離即可（範例程式碼用的是前者）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
