This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
from collections import deque, defaultdict
def min_jumps_to_pass_news(N, M, doges):
# Create adjacency list for the graph based on doge jumps
graph = defaultdict(list)
for b, p in doges:
if 0 <= b < N:
if 0 <= b + p < N:
graph[b].append(b + p)
if 0 <= b - p < N:
graph[b].append(b - p)
# BFS to find the shortest path
queue = deque([0]) # Start BFS from skyscraper 0
visited = [False] * N
distance = [float('inf')] * N
visited[0] = True
distance[0] = 0
while queue:
current = queue.popleft()
current_dist = distance[current]
for neighbor in graph[current]:
if not visited[neighbor]:
visited[neighbor] = True
distance[neighbor] = current_dist + 1
queue.append(neighbor)
# Check the distance to skyscraper 1
if distance[1] == float('inf'):
return -1
return distance[1]
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |