43 lines
831 B
Python
43 lines
831 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[a][b] = IntSet(x, y + 1)
|
|
|
|
ranges = defaultdict(lambda: NONE)
|
|
ranges[S] = ALL
|
|
|
|
q = deque([S])
|
|
|
|
while q:
|
|
if len(ranges[D]) == B:
|
|
break
|
|
|
|
curr = q.pop()
|
|
|
|
# if curr == D:
|
|
# continue
|
|
|
|
for neighbor, r in rooms[curr].items():
|
|
old = ranges[neighbor]
|
|
new = ranges[neighbor] | ranges[curr] & r
|
|
if old != new:
|
|
# try:
|
|
# q.remove(neighbor)
|
|
# except ValueError:
|
|
# pass
|
|
q.append(neighbor)
|
|
ranges[neighbor] = new
|
|
|
|
print(len(ranges[D]))
|