aboutsummaryrefslogtreecommitdiff
path: root/second_min_time_dest.py
diff options
context:
space:
mode:
Diffstat (limited to 'second_min_time_dest.py')
-rw-r--r--second_min_time_dest.py56
1 files changed, 56 insertions, 0 deletions
diff --git a/second_min_time_dest.py b/second_min_time_dest.py
new file mode 100644
index 0000000..adf08da
--- /dev/null
+++ b/second_min_time_dest.py
@@ -0,0 +1,56 @@
+# 2045. Second Minimum Time to Reach destination
+from collections import defaultdict
+import heapq
+from math import ceil
+
+"""
+a city is represented as a bi directional connected graph with 'n' vertices
+where each vertex is labeled from 1 to 'n' inclusively. the edges in the
+graph are represented as a 2d integer array 'edges' where each 'edges[i] =
+[ui, vi]' denotes a bi directional edge between vertex 'ui' and vertex 'vi'.
+every vertex pair is connected by at most one edge, and no vertex has an edge
+to itself. the time taken to traverse any edge is 'time' minutes. each vertex
+has a traffic signal which changes its colour from green to red and vice
+versa every 'change' minutes. all signals change at the same time. you can
+entre a vertex at any time, but can leave a vertex only when the signal is
+green. you cannot wait at a vertex if the signal is green.
+"""
+
+
+class Solution(object):
+ def secondMinimum(self, n, edges, time, change):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :type time: int
+ :type change: int
+ :rtype: int
+ """
+ d = [[] for _ in range(n + 1)]
+ d[1] = [0]
+ g, heap = defaultdict(list), [(0, 1)]
+ for a, b in edges:
+ g[a] += [b]
+ g[b] += [a]
+ while heap:
+ min_dist, idx = heapq.heappop(heap)
+ if idx == n and len(d[n]) == 2:
+ return max(d[n])
+ for neib in g[idx]:
+ if (min_dist // change) % 2 == 0:
+ cand = min_dist + time
+ else:
+ cand = ceil(min_dist / (2 * change)) * (2 * change) + time
+ if not d[neib] or (len(d[neib]) == 1 and d[neib] != [cand]):
+ d[neib] += [cand]
+ heapq.heappush(heap, (cand, neib))
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.secondMinimum(
+ n=5, edges=[[1, 2], [1, 3], [1, 4], [3, 4], [4, 5]], time=3, change=5
+ )
+ )
+ print(obj.secondMinimum(n=2, edges=[[1, 2]], time=3, change=2))