## [課程安排 IV](https://leetcode-cn.com/problems/course-schedule-iv/) #### 思路 這道題在周賽的時候卡了我很久，簡單分享一下我的思路吧。構建一張表，index代表課程，他的值為改課程所有的先修課程，如圖： ``` 示例： n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]] 構造表，如下： index value 0 → null 1 → 0 2 2 → null ``` 遍歷該表就能知道，是否為先修課程。但是實際做的過程中發現，我需要不斷遍歷更新這張表，才能獲取正確的值。因為，先修課程可能不是直接聯系的，可能中間還隔了好幾個。 雖然AC了，但是代碼非常糟糕。主要也是因為思路太糟糕。 （補，其實有點鄰接表的那個意思了，但是當時對我來說超綱了） **拜讀大佬解法，獲得新知識: Floyd-Warshall 算法** > 相關文章： > [https://brilliant.org/wiki/floyd-warshall-algorithm/](https://brilliant.org/wiki/floyd-warshall-algorithm/) > [https://juejin.im/post/5cc79c93f265da035b61a42e](https://juejin.im/post/5cc79c93f265da035b61a42e) > [https://houbb.github.io/2020/01/23/data-struct-learn-03-graph-floyd](https://houbb.github.io/2020/01/23/data-struct-learn-03-graph-floyd) 花半天時間搞懂了，只能說真的是相當精彩！小伙伴可以看上面的鏈接，基本都看完應該就能理解了。AC！ #### 代碼 python3 ``` class Solution: def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: dp = [[False] * n for _ in range(n)] for i,j in prerequisites: dp[i][j] = True for k in range(n): for i in range(n): for j in range(n): dp[i][j] = (dp[i][k] and dp[k][j]) or dp[i][j] return [dp[r][c] for r,c in queries] ```