結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 14:26:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,714 ms / 2,000 ms |
コード長 | 1,280 bytes |
コンパイル時間 | 242 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 150,712 KB |
最終ジャッジ日時 | 2025-09-06 14:27:18 |
合計ジャッジ時間 | 14,409 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N,M = map(int,input().split()) nodes = [] for i in range(M): a,b = map(int,input().split()) nodes.append((a-1,b-1)) K = int(input()) if K > 0: A = list(map(int,input().split())) else: A = [] iwaiset = set() for i in A: iwaiset.add(i-1) node = [[] for _ in range(5*N)] for a,b in nodes: if b in iwaiset: node[a].append(b+N) node[a+N].append(b+N*2) node[a+N*2].append(b+N*3) node[a+N*3].append(b+N*4) else: node[a].append(b) node[a+N].append(b) node[a+N*2].append(b) node[a+N*3].append(b) node[a+N*4].append(b) if a in iwaiset: node[b].append(a+N) node[b+N].append(a+N*2) node[b+N*2].append(a+N*3) node[b+N*3].append(a+N*4) else: node[b].append(a) node[b+N].append(a) node[b+N*2].append(a) node[b+N*3].append(a) node[b+N*4].append(a) dist = [10**18 for _ in range(5*N)] dist[0] = 0 queue = [0] while queue: v = queue.pop(0) for u in node[v]: if dist[u] == 10**18: dist[u] = dist[v] + 1 queue.append(u) print(min(dist[N-1],dist[2*N-1],dist[3*N-1],dist[4*N-1],dist[5*N-1]) if min(dist[N-1],dist[2*N-1],dist[3*N-1],dist[4*N-1],dist[5*N-1]) != 10**18 else -1)