結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー Yakumo221
提出日時 2025-09-06 13:30:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 335 ms / 2,000 ms
コード長 1,051 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 106,960 KB
最終ジャッジ日時 2025-09-06 13:30:42
合計ジャッジ時間 7,626 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,m  = map(int, input().split())
uv = []
graph = [[] for i in range(n)]

for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    uv.append((u,v))
    graph[u].append(v)
    graph[v].append(u)



k = int(input())
if k == 0:
    alist = []
else:
    alist = list(map(lambda x: int(x)-1, input().split()))

# x回遭遇した状態でyにいる: x*n + y
dist = [1 << 60 for i in range(5 * n)]
dist[0] = 0

check = [0 for i in range(n)]
for a in alist:
    check[a] = 1

que = [0]
while que:
    nq = []
    while que:
        val = que.pop()
        x,y = divmod(val, n)
        if y == (n-1):
            print(dist[val])
            exit()

        for ny in graph[y]:
            if check[ny]:
                nx = x+1
            else:
                nx = 0
            
            if nx >= 5:
                continue

            nval = nx * n + ny

            if dist[nval] <= (dist[val] + 1):
                continue
            dist[nval] = dist[val]+1

            nq.append(nval)
    
    que = nq

print(-1)
0