aboutsummaryrefslogtreecommitdiff
path: root/second_min_time_dest.py
blob: adf08da7ef80cda673f195c21d1c52403411e524 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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))