• Leetcode 3604. Minimum Time to Reach Destination in Directed Graph
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3604. Minimum Time to Reach Destination in Directed Graph

1. 解題思路

這一題思路上就是一個廣度優先遍歷，我們不斷考察當前時間點以及位置的情況下，下一個點可行的位置，然后考察最近的時間點能夠到達的位置，遍歷全部可能性直至達到目標位置即可。

2. 代碼實現

給出python代碼實現如下：

class Solution:def minTime(self, n: int, edges: List[List[int]]) -> int:graph = defaultdict(list)for u, v, st, ed in edges:graph[u].append((v, st, ed))q = [(0, 0)]seen = set()while q:t, u = heapq.heappop(q)if u == n-1:return tif u in seen:continueseen.add(u)for v, st, ed in graph[u]:if t > ed or v in seen:continueheappush(q, (max(t+1, st+1), v))return -1

提交代碼評測得到：耗時234ms，占用內存72.14MB。