AlgorithmAndLeetCode · pull · Jul 7, 2025 · Jul 7, 2025 · Jul 7, 2025 · Jul 7, 2025
diff --git a/...estination-in-Directed-Graph/3604.Minimum-Time-to-Reach-Destination-in-Directed-Graph.cpp b/...estination-in-Directed-Graph/3604.Minimum-Time-to-Reach-Destination-in-Directed-Graph.cpp
@@ -0,0 +1,41 @@
+struct state {
+    int node, time;
+    bool operator<(state const& o) const {
+        return time > o.time;
+    }
+};
+class Solution {
+    vector<vector<int>>next[100005];
+public:
+    int minTime(int n, vector<vector<int>>& edges) {
+        for (auto& e:edges) {
+            int u=e[0], v=e[1], start=e[2], end=e[3];
+            next[u].push_back({v, start, end});
+        }
+
+        vector<int>visited(n, -1);
+        priority_queue<state>pq;
+        pq.push({0,0});
+
+        while (!pq.empty()) {
+            auto [node, time] = pq.top();
+            // cout<<node<<" "<<time<<endl;
+            pq.pop();
+            if (visited[node]!=-1) continue;
+            visited[node] = time;
+            if (node==n-1) return time;
+
+            for (auto nxt: next[node]) {
+                int v = nxt[0], s = nxt[1], e = nxt[2];
+                if (time < s && (visited[v]==-1 || visited[v]>s+1)) {
+                    pq.push({v, s+1});
+                }
+                if (time >= s && time <=e && (visited[v]==-1 || visited[v]>time+1)) {
+                    pq.push({v, time+1});
+                }
+            }
+        }
+
+        return -1;        
+    }
+};
diff --git a/BFS/3604.Minimum-Time-to-Reach-Destination-in-Directed-Graph/Readme.md b/BFS/3604.Minimum-Time-to-Reach-Destination-in-Directed-Graph/Readme.md
@@ -0,0 +1,12 @@
+### 3604.Minimum-Time-to-Reach-Destination-in-Directed-Graph
+
+常规的Dijkstra的模版题。本题优先队里的元素需要定义状态
+```cpp
+struct state {
+    int node, time;
+    bool operator<(state const& o) const {
+        return time > o.time;
+    }
+};
+```
+对于出队列的一个状态{node,time}，我们可知到达node的最短时间就是time。然后我们检查它周围的路径{v,start,end}。如果time<start，那么我们就把{v,start+1}加入优先队列。如果time在[start,end]时段内，那么我们就把{v,time+1}加入优先队列。
diff --git a/Readme.md b/Readme.md
@@ -670,6 +670,7 @@
 [2203.Minimum-Weighted-Subgraph-With-the-Required-Paths](https://github.com/wisdompeak/LeetCode/tree/master/BFS/2203.Minimum-Weighted-Subgraph-With-the-Required-Paths) (H-)     
 [2473.Minimum-Cost-to-Buy-Apples](https://github.com/wisdompeak/LeetCode/tree/master/BFS/2473.Minimum-Cost-to-Buy-Apples) (M)      
 [3594.Minimum-Time-to-Transport-All-Individuals](https://github.com/wisdompeak/LeetCode/tree/master/BFS/3594.Minimum-Time-to-Transport-All-Individuals) (H)      
+[3604.Minimum-Time-to-Reach-Destination-in-Directed-Graph](https://github.com/wisdompeak/LeetCode/tree/master/BFS/3604.Minimum-Time-to-Reach-Destination-in-Directed-Graph) (M+)      
 * ``Dijkstra (for Bipatite Graph)``   
 [1066.Campus-Bikes-II](https://github.com/wisdompeak/LeetCode/tree/master/BFS/1066.Campus-Bikes-II) (H+)    
 [1879.Minimum-XOR-Sum-of-Two-Arrays](https://github.com/wisdompeak/LeetCode/tree/master/BFS/1879.Minimum-XOR-Sum-of-Two-Arrays) (H)