Solution to LeetCode 2045 Second Minimum Time to Reach Destination.
LeetCode 2045
Second Minimum Time to Reach Destination (Hard). [link]
The time to arrival at the next node can be calculated by: t_i+1 = t_i + waitTime + time.
The wait time at (i+1) node can be calculated by: If t mod (2 * change) within [0, change), waitTime = 0 (departure before the node gets red). If t mod (2 * change) within [change, 2 * change), waitTime = 2 * change - t mod (2 * change) (departure after the node gets red).
Time complexity O(V + E). Space complexity O(V + E).
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
"""
graph = [[] for _ in range(n+1)]
for edge in edges: # construct a bi-directional connected graph
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
# dist[i][0] is the shortest path from 1 to i
# dust[i][1] is the second shortest path from 1 to i
dist = [[float('inf')] * 2 for _ in range(n+1)]
dist[1][0] = 0
q = deque([(1,0)]) # store next node and the edge number for BFS
while dist[n][1] == float('inf'):
p = q.popleft()
for y in graph[p[0]]: # for all next node
d = p[1] + 1 # count the edge number
if d < dist[y][0]: # find the shortest
dist[y][0] = d
q.append((y,d)) # append the next node to queue
elif dist[y][0] < d < dist[y][1]: # second shortest
dist[y][1] = d
q.append((y,d)) # append the next node to queue
res = 0
for _ in range(dist[n][1]): # total number of edges (second shortest)
if res % (2 * change) >= change: # wait time
res += change * 2 - res % (2 * change)
res += time # cost time on the way
return res
