本次題目來自于卡碼網

???97. 小明逛公園?（Floyd 算法精講）

1、確定dp數組以及下標的含義

grid[i][j][k] = m，表示 節點i 到 節點j 以[1...k] 集合為中間節點的最短距離為m

2、確定遞推公式

分兩種情況：

• 節點i 到 節點j 的最短路徑經過節點k
• 節點i 到 節點j 的最短路徑不經過節點k

對于第一種情況，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]

第二種情況，grid[i][j][k] = grid[i][j][k - 1]

因為我們是求最短路，對于這兩種情況自然是取最小值。

即：?grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

3、dp數組如何初始化

把k 賦值為 0，本題 節點0 是無意義的，節點是從1 到 n

初始化代碼

vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // C++定義了一個三位數組，10005是因為邊的最大距離是10^4for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2][0] = val;grid[p2][p1][0] = val; // 注意這里是雙向圖
} 

grid數組中其他元素數值應該初始化多少呢？ 本題求的是最小值，所以輸入數據沒有涉及到的節點的情況都應該初始為一個最大數。

4、確定遍歷順序

我們來看初始化，我們是把 k =0 的 i 和j 對應的數值都初始化了，這樣才能去計算 k = 1 的時候 i 和 j 對應的數值。

這就好比是一個三維坐標，i 和j 是平層，而k 是 垂直向上 的。

遍歷的順序是從底向上 一層一層去遍歷。

所以遍歷k 的for循環一定是在最外面，這樣才能一層一層去遍歷

5、舉例推導dp數組

if __name__ == '__main__':n, m = map(int, input().split())grid = [[[10005] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]  # 因為邊的最大距離是10^4for i in range(m):p1, p2, val = map(int, input().split())grid[p1][p2][0] = valgrid[p2][p1][0] = val  # 雙向圖# 開始 floydfor k in range(1, n + 1):for i in range(1, n + 1):for j in range(n + 1):grid[i][j][k] = min(grid[i][j][k - 1], grid[i][k][k - 1] + grid[k][j][k - 1])# 輸出結果z = int(input())for _ in range(z):start, end = map(int, input().split())if grid[start][end][n] == 10005:print(-1)else:print(grid[start][end][n])

空間優化

我們可以做一下 空間上的優化，從滾動數組的角度來看，我們定義一個 grid[n + 1][ n + 1][2] 這么大的數組就可以，因為k 只是依賴于 k-1的狀態，并不需要記錄k-2，k-3，k-4 等等這些狀態。

又由于本層計算中，使用了本層計算過的 grid[i][k] 和 grid[k][j] 是沒問題的。那么就沒必要區分，grid[i][k] 和 grid[k][j] 是 屬于 k - 1 層的呢，還是 k 層的。

if __name__ == '__main__':n, m = map(int, input().split())grid = [[10005] * (n + 1) for _ in range(n + 1)]  # 因為邊的最大距離是10^4for i in range(m):p1, p2, val = map(int, input().split())grid[p1][p2] = valgrid[p2][p1] = val  # 雙向圖# 開始 floydfor k in range(1, n + 1):for i in range(1, n + 1):for j in range(n + 1):grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])# 輸出結果z = int(input())for _ in range(z):start, end = map(int, input().split())if grid[start][end] == 10005:print(-1)else:print(grid[start][end])

126. 騎士的攻擊?（A * 算法精講）

加入了啟發式函數，使用了優先隊列，優先隊列中自定義了比較函數(https://www.cnblogs.com/xrszff/p/14783972.html)

import heapq# F = G + H
# G = 從起點到該節點路徑消耗
# H = 該節點到終點的預估消耗class Knight:def __init__(self):self.x = 0self.y = 0self.g = 0self.h = 0self.f = 0def __lt__(self, other):  # 自定義比較函數return self.f < other.fdef heuristic(k):  # 歐拉距離return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2)  # 統一不開根號，這樣可以提高精度def astar(k):heapq.heappush(que, k)while que:cur = heapq.heappop(que)if cur.x == b1 and cur.y == b2:breakfor i in range(8):next = Knight()next.x = cur.x + dir[i][0]next.y = cur.y + dir[i][1]if next.x < 1 or next.x > 1000 or next.y < 1 or next.y > 1000:continueif moves[next.x][next.y] == 0:moves[next.x][next.y] = moves[cur.x][cur.y] + 1# 開始計算Fnext.g = cur.g + 5  # 統一不開根號，這樣可以提高精度，馬走日，1 * 1 + 2 * 2 = 5next.h = heuristic(next)next.f = next.g + next.hheapq.heappush(que, next)if __name__ == '__main__':dir = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)]que = []heapq.heapify(que)n = int(input())for _ in range(n):a1, a2, b1, b2 = map(int, input().split())moves = [[0] * 1001 for _ in range(1001)]  # 每次重新開辟空間start = Knight()start.x = a1start.y = a2start.g = 0start.h = heuristic(start)start.f = start.g + start.hastar(start)while que:heapq.heappop(que)  # 隊列清空print(moves[b1][b2])