結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:07:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 637 ms / 2,000 ms |
コード長 | 1,531 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 81,832 KB |
実行使用メモリ | 159,348 KB |
最終ジャッジ日時 | 2025-09-06 14:07:36 |
合計ジャッジ時間 | 12,970 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
def IM(): return map(int, input().split()) N, M = IM() G = [[] for _ in range(5*N)] nodes = [] for _ in range(M): u, v = IM() u -= 1 v -= 1 nodes.append((u, v)) C = int(input()) if C: A = set(IM()) else: A = set() for i in range(M): u, v = nodes[i] if u+1 in A: for j in range(4): G[N*j+v].append(N*(j+1)+u) else: for j in range(5): G[N*j+v].append(u) if v+1 in A: for j in range(4): G[N*j+u].append(N*(j+1)+v) else: for j in range(5): G[N*j+u].append(v) # 各頂点が何手目に探索されたか # -1 は「まだ探索されていない」ことを表す dist = [-1] * (5*N) # k 手目に探索された頂点集合を格納 (最大でも N-1 手まで) nodes = [[] for i in range(5*N)] # 頂点 0 を始点とする dist[0] = 0 nodes[0] = [0] # k 手目の探索をする for k in range(1, 5*N): # k-1 手目に探索された各頂点 v に対して for v in nodes[k - 1]: # 頂点 v から 1 手で行ける頂点 next_v を探索 for next_v in G[v]: # 頂点 next_v が探索済みであれば何もしない if dist[next_v] != -1: continue # 頂点 next_v を探索する dist[next_v] = dist[v] + 1 nodes[k].append(next_v) #print(dist) ans = 10**18 for i in range(5): if dist[N*i+N-1] != -1: ans = min(ans, dist[N*i+N-1]) print(ans if ans != 10**18 else -1)