結果

問題 No.3263 違法な散歩道
ユーザー yt142857
提出日時 2025-09-06 13:42:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,264 bytes
コンパイル時間 230 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 273,684 KB
最終ジャッジ日時 2025-09-06 13:43:05
合計ジャッジ時間 12,392 ms
ジャッジサーバーID
（参考情報） 		judge / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,m = map(int,input().split())
graph = {}
for i in range(n):
  graph[i+1] = []
for i in range(m):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
iwai_num = int(input())
if iwai_num != 0:
  iwai = [int(_) for _ in input().split()]
else:
  iwai = []
iwai = set(iwai)
non_iwai = []
for i in range(1,n+1):
  if i not in iwai:
    non_iwai.append(i)
graph2 = {}
for i in range(n):
  graph2[i+1] = []
from collections import deque
for i in non_iwai:
  queue = deque()
  queue.append((i,0))
  visited = set()
  visited.add(i)
  ok = []
  while queue:
    node,dis = queue.popleft()
    if dis > 5:
      break
    if node not in iwai:
      ok.append((node,dis))
    for nei in graph[node]:
      if nei not in visited:
        visited.add(nei)
        queue.append((nei,dis+1))
  for j,dis in ok:
    if i != j:
      graph2[i].append((dis,j))
import heapq
kakutei = [False]*(n+1)
heap = [(0,1)]
cur = [float('inf')]*(n+1)
cur[1] = 0
while heap:
  n_dis,node = heapq.heappop(heap)
  if kakutei[node]:
    continue
  kakutei[node] = True
  for n_dis,nei in graph2[node]:
    if cur[node]+n_dis < cur[nei]: 
      heapq.heappush(heap,(cur[node]+n_dis,nei))
      cur[nei] = cur[node]+n_dis
if cur[n] == float('inf'):
  cur[n] = -1
print(cur[n])
0