結果
問題 |
No.2565 はじめてのおつかい
|
ユーザー |
|
提出日時 | 2024-04-09 23:43:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 766 ms / 2,000 ms |
コード長 | 772 bytes |
コンパイル時間 | 315 ms |
コンパイル使用メモリ | 82,092 KB |
実行使用メモリ | 96,264 KB |
最終ジャッジ日時 | 2024-10-02 00:39:46 |
合計ジャッジ時間 | 24,172 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
import heapq n, m = map(int, input().split()) edges = [[] for _ in range(n)] for _ in range(m): u, v = map(int, input().split()) u, v = u - 1, v - 1 edges[u].append(v) INF = float("inf") def dijkstra(s, g): dist = [INF] * n que = [(0, s)] heapq.heapify(que) while que: cost, crt = heapq.heappop(que) if dist[crt] <= cost: continue dist[crt] = cost for nxt in edges[crt]: if dist[nxt] <= cost + 1: continue heapq.heappush(que, (cost + 1, nxt)) return dist[g] ans = INF for l in ((0, n - 1, n - 2, 0), (0, n - 2, n - 1, 0)): tmp = 0 for a, b in zip(l, l[1:]): tmp += dijkstra(a, b) ans = min(ans, tmp) print(-1 if ans == INF else ans)