Second Minimum Time to Reach Destination — LeetCode 2045 Python Solution
HardBreadth-First SearchGraphShortest Path
- Problem
- #2045
- Pattern
- Breadth-First Search
- Reading time
- 5 min
- Source
- leetcode.com
The problem
A city is represented as a bi-directional connected graph with n vertices where each vertex is labeled from 1 to n (inclusive). 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.
Example
- Input
- n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
- Output
- 13
- Explanation
- The figure on the left shows the given graph.
Python solution
Python
class Solution:
def secondMinimum(
self, n: int, edges: List[List[int]], time: int, change: int
) -> int:
g = defaultdict(set)
for u, v in edges:
g[u].add(v)
g[v].add(u)
q = deque([(1, 0)])
dist = [[inf] * 2 for _ in range(n + 1)]
dist[1][1] = 0
while q:
u, d = q.popleft()
for v in g[u]:
if d + 1 < dist[v][0]:
dist[v][0] = d + 1
q.append((v, d + 1))
elif dist[v][0] < d + 1 < dist[v][1]:
dist[v][1] = d + 1
if v == n:
break
q.append((v, d + 1))
ans = 0
for i in range(dist[n][1]):
ans += time
if i < dist[n][1] - 1 and (ans // change) % 2 == 1:
ans = (ans + change) // change * change
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(V) auxiliary |
Pattern: Breadth-First Search
Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 2045. Second Minimum Time to Reach Destination is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.
The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2045. Second Minimum Time to Reach Destination?
- LeetCode 2045. Second Minimum Time to Reach Destination is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2045. Second Minimum Time to Reach Destination?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 2045. Second Minimum Time to Reach Destination?
- The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 2045. Second Minimum Time to Reach Destination cover?
- LeetCode 2045. Second Minimum Time to Reach Destination is tagged Breadth-First Search, Graph and Shortest Path on LeetCode.