Problem statement

https://leetcode.com/problems/second-minimum-time-to-reach-destination/

Solution

To solve this problem you need to understand how Dijkstra algorithm work and adapt it to find the second shortest path. In usual Dijkstra algorithm for each node we keep shortest distance so far for this node. Here we need to keep two shortest distances. So, we keep in D[node] list of shortest distances for node.

  1. First we traverse our edges and construct graph G.
  2. Then we do the classical Dijkstra with heap, where we extract min_dist, idx = heappop(heap).
  3. We check if we already found two different distances for node n and if we found, return biggest distance among these two.
  4. Iterate through all neighbours and calculate distance for candidates: if we go on green light, just add time, if we are on the red ligth, wait for green: for the smallest time divisible by 2*change, such that it is greater or equal to min_dist.
  5. Now, if we visit our neib for the first time, we update distance. If we visited it only once and new candidate is not equal to what we already have, add it to distances. Finally, if we already have two different distances for this node, we try to visit it only if new candidate is less than maximum (and not equal to minimum) that is we can update distances. update: in fact this condition is not needed, because we use greedy strategy here: for each node we first find the smallest distance and then the next smallest.

Complexity

It is almost like classical Dijkstra algorithm, but now we can revisit some nodes from time to time. Time complexity is still O((E + V) * log V) though, because we have no more than 2 candidates, space complexity is O(E + V).

Code

class Solution:
    def secondMinimum(self, n, edges, time, change):
        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 = 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]
                    heappush(heap, (cand, neib))