結果
問題 |
No.2565 はじめてのおつかい
|
ユーザー |
![]() |
提出日時 | 2024-10-18 14:03:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 187 ms / 2,000 ms |
コード長 | 935 bytes |
コンパイル時間 | 5,536 ms |
コンパイル使用メモリ | 82,084 KB |
実行使用メモリ | 92,384 KB |
最終ジャッジ日時 | 2024-10-18 14:03:42 |
合計ジャッジ時間 | 11,246 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
N,M = map(int,input().split()) G = [[] for i in range(N)] for _ in range(M): u,v = map(int,input().split()) G[u - 1].append(v - 1) from collections import deque def get_dist(start, goal, G, N): q = deque([]) q.append([start, 0]) visited = [False] * N visited[start] = True while q: v, d = q.popleft() for child in G[v]: if visited[child]: continue visited[child] = True if child == goal: return d + 1 q.append([child, d + 1]) return -1 D = [0, N - 2, N - 1] routes = ((0,1,2,0),(0,2,1,0)) INF = 1 << 60 ans = INF for route in routes: d = 0 for i in range(len(route) - 1): dist = get_dist(D[route[i]], D[route[i + 1]], G, N) if dist == -1: break d += dist else: ans = min(ans, d) if ans == INF: print(-1) else: print(ans)