結果

問題 No.3263 違法な散歩道
ユーザー dokukuma
提出日時 2025-09-06 14:01:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 377 ms / 2,000 ms
コード長 1,210 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 81,764 KB
実行使用メモリ 110,784 KB
最終ジャッジ日時 2025-09-06 14:01:53
合計ジャッジ時間 8,022 ms
ジャッジサーバーID
(参考情報)
judge1 / judge
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys, time, random, heapq, math, itertools, copy
from collections import deque, Counter, defaultdict
from bisect import bisect, bisect_left, bisect_right
import heapq as hq
from functools import cache, cmp_to_key
def debug(*x):print('debug:',*x, file=sys.stderr)
sys.setrecursionlimit(300000)
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 61 - 1
mod = 998244353
dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]

N, M = mi()
g = [[] for _ in range(N)] 
for i in range(M):
    u, v = mi()
    u -= 1; v -= 1
    g[u].append(v)
    g[v].append(u)
K = ii()
if K != 0:
    A = li()
else:
    A = []
for i in range(K):
    A[i] -= 1
A = set(A)
visited = [[False] * N for _ in range(5)]
d = deque()
d.append((0, 0, 0))  #depth, startnode, cnt
visited[0][0] = True
while d:
    depth, node, cnt = d.popleft()
    if node == N-1:
        print(cnt)
        exit()
    for k in g[node]:
        if visited[depth][k]: continue
        visited[depth][k] = True
        if k not in A:
            d.append((0, k, cnt + 1))
        else:
            if depth < 4:
                d.append((depth + 1, k, cnt+1))
    
print(-1)
0