43 lines
841 B
Python
43 lines
841 B
Python
from collections import deque, defaultdict
|
|
from intset import IntSet
|
|
|
|
N, L, B = map(int, input().split())
|
|
|
|
S, D = map(int, input().split())
|
|
|
|
rooms = defaultdict(dict)
|
|
|
|
ALL = IntSet(1, B + 1)
|
|
NONE = IntSet()
|
|
|
|
for i in range(L):
|
|
a, b, x, y = map(int, input().split())
|
|
rooms[b][a] = IntSet(x, y + 1)
|
|
|
|
ranges = defaultdict(lambda: NONE)
|
|
ranges[D] = ALL
|
|
|
|
q = [D]
|
|
|
|
while q:
|
|
# if len(ranges[D]) == B:
|
|
# break
|
|
|
|
curr = q.pop(0)
|
|
|
|
# if curr == D:
|
|
# continue
|
|
|
|
for neighbor, r in rooms[curr].items():
|
|
old = ranges[neighbor]
|
|
new = ranges[neighbor] | (ranges[curr] & r)
|
|
if len(old) != len(new):
|
|
# try:
|
|
# q.remove(neighbor)
|
|
# except ValueError:
|
|
# pass
|
|
q.append(neighbor)
|
|
ranges[neighbor] = new
|
|
|
|
print(len(ranges[S]))
|