結果

問題 No.3263 違法な散歩道
ユーザー ts5208
提出日時 2025-09-06 13:26:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 555 ms / 2,000 ms
コード長 1,417 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,800 KB
実行使用メモリ 119,648 KB
最終ジャッジ日時 2025-09-06 13:27:24
合計ジャッジ時間 10,160 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappop, heappush, heapify
from bisect import bisect
#from sortedcontainers import SortedList
from collections import deque, defaultdict
from math import floor, ceil, isqrt, comb
from sys import stdin, setrecursionlimit
#setrecursionlimit(10**7)
intin = lambda: int(stdin.readline())
strin = lambda: stdin.readline().rstrip()
listin = lambda: list(map(int, stdin.readline().split()))
tuplein = lambda m: [tuple(map(lambda x: int(x) if x.isdigit() or (len(x) > 1 and x[0] == "-" and x[1:].isdigit()) else x, stdin.readline().split())) for _ in range(m)]
gridin = lambda m: [list(map(int, stdin.readline().split())) for _ in range(m)]
strgridin = lambda h: [stdin.readline().rstrip() for _ in range(h)]
mapin = lambda: map(int, stdin.readline().split())
N, M = mapin()
UV = tuplein(M)
K = intin()
A = listin()
graph = [[] for _ in range(N)]
for u, v in UV:
    u -= 1; v -= 1
    graph[u].append(v)
    graph[v].append(u)
for i in range(K): A[i] -= 1
A = set(A)
dist = [[float("inf")] * 5 for _ in range(N)]
dist[0][0] = 0
queue = deque([(0, 0)])
while queue:
    pos, cnt = queue.popleft()
    for edge in graph[pos]:
        ncnt = cnt + 1 if edge in A else 0
        if ncnt >= 5:
            continue
        if dist[edge][ncnt] == float("inf"):
            dist[edge][ncnt] = dist[pos][cnt] + 1
            queue.append((edge, ncnt))
ans = min(dist[-1])
print(ans if ans != float("inf") else -1)
0