Submission #56299356

---

Source Code Expand

import heapq
from collections import defaultdict

N = int(input())

y_coords = set()
L = []
U = []
for _ in range(N):
    l, u = map(int, input().split())
    L.append(l)
    U.append(u)
    y_coords.add(l)
    y_coords.add(u)

Q = int(input())
queries = []
for _ in range(Q):
    sx, sy, tx, ty = map(int, input().split())
    queries.append((sx, sy, tx, ty))
    y_coords.add(sy)
    y_coords.add(ty)

y_coords = sorted(list(y_coords))
y_map = {y: i for i, y in enumerate(y_coords)}
y_map_inv = {i: y for y, i in y_map.items()}

graph = defaultdict(list)
for x in range(1, N + 1):
    for y in range(y_map[L[x - 1]], y_map[U[x - 1]] + 1):
        if x > 1:
            graph[(x - 1, y)].append((x, y))
            graph[(x, y)].append((x - 1, y))
        if y > y_map[L[x - 1]]:
            graph[(x, y)].append((x, y - 1))
            graph[(x, y - 1)].append((x, y))
        if y < y_map[U[x - 1]]:
            graph[(x, y)].append((x, y + 1))
            graph[(x, y + 1)].append((x, y))

def dijkstra(start, end):
    queue = [(0, start)]
    dist = {start: 0}
    while queue:
        current_dist, (x, y) = heapq.heappop(queue)
        if (x, y) == end:
            return current_dist
        if current_dist > dist[(x, y)]:
            continue
        for nx, ny in graph[(x, y)]:
            cost = 1 if x != nx else abs(y_map_inv[ny] - y_map_inv[y])
            new_dist = current_dist + cost
            if (nx, ny) not in dist or new_dist < dist[(nx, ny)]:
                dist[(nx, ny)] = new_dist
                heapq.heappush(queue, (new_dist, (nx, ny)))
    return -1

for sx, sy, tx, ty in queries:
    sy_compressed = y_map[sy]
    ty_compressed = y_map[ty]
    start = (sx, sy_compressed)
    end = (tx, ty_compressed)
    print(dijkstra(start, end))

Submission Info

Judge Result