結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 13:20:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 605 ms / 2,000 ms |
コード長 | 786 bytes |
コンパイル時間 | 221 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 115,072 KB |
最終ジャッジ日時 | 2025-09-06 13:20:44 |
合計ジャッジ時間 | 11,824 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N,M=map(int,input().split()) G=[[] for i in range(N)] for i in range(M): a,b=map(int,input().split()) G[a-1].append(b-1) G[b-1].append(a-1) K=int(input()) u=[False]*N if K>0: B=list(map(int,input().split())) for i in range(K): u[B[i]-1]=True dp=[[10**10]*5 for i in range(N)] dp[0][0]=0 from heapq import heappush,heappop S=[] heappush(S,0) kaku=[[False]*5 for i in range(N)] while S: w=heappop(S) cost=w//(10**6) w-=cost*10**6 pos=w//5 t=w%5 if kaku[pos][t]==True: continue kaku[pos][t]=True for y in G[pos]: t2=t if u[y]==True: t2+=1 else: t2=0 if t2<5: if dp[y][t2]>dp[pos][t]+1: dp[y][t2]=dp[pos][t]+1 heappush(S,(dp[y][t2])*10**6+y*5+t2) result=dp[N-1][0] if result>10**9: result=-1 print(result)