加了一维状态(持有钥匙的状态)的dj
from collections import defaultdict
from heapq import heappop, heappush
from math import inf
n, m, p = map(int, input().split())
k = int(input())
g = defaultdict(lambda :-1)
for _ in range(k):
x1, y1, x2, y2, t = map(int, input().split())
g[x1, y1, x2, y2] = t
g[x2, y2, x1, y1] = t
w = defaultdict(int)
for _ in range(int(input())):
x, y, q = map(int, input().split())
w[x,y] |= (1 << q)
def dj():
dis = defaultdict(lambda: inf)
dis[1,1,0] = 0
q = [(0, 1, 1, 0)]
#ans = inf
while q:
# print(q)
d, x, y, s = heappop(q)
if dis[x,y,s] < d:
continue
if (x,y) == (n,m):
return d
# 拿上钥匙
s |= w[x,y]
for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):
if 1 <= nx <= n and 1 <= ny <= m:
if g[x,y,nx,ny] == 0:
continue
elif (g[x,y,nx,ny] == -1 or (1 << g[x,y,nx,ny]) & s) and dis[nx,ny,s] > d + 1:
dis[nx, ny, s] = d + 1
heappush(q, (d + 1, nx, ny, s))
return -1
print(dj())