結果
| 問題 | No.2565 はじめてのおつかい |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-12 09:17:39 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 394 ms / 2,000 ms |
| + 49µs | |
| コード長 | 1,132 bytes |
| 記録 | |
| コンパイル時間 | 83 ms |
| コンパイル使用メモリ | 64,636 KB |
| 実行使用メモリ | 78,296 KB |
| 最終ジャッジ日時 | 2026-11-12 09:18:23 |
| 合計ジャッジ時間 | 16,457 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge3_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 50 |
ソースコード
import heapq
N, M = (int(x) for x in input().split())
d = [[] for i in range(N)]
for i in range(M):
u, v = (int(x) for x in input().split())
d[u-1].append(v)
INF = 10**18
dist1, dist2, dist3 = [INF]*N, [INF]*N, [INF]*N
L = []
heapq.heapify(L)
heapq.heappush(L, [0, 1])
dist1[1-1] = 0
while L:
c, u = heapq.heappop(L)
if dist1[u-1] < c:
continue
for v in d[u-1]:
if dist1[v-1] > c+1:
dist1[v-1] = c+1
heapq.heappush(L, [c+1, v])
L = []
heapq.heapify(L)
heapq.heappush(L, [0, N-1])
dist2[N-1-1] = 0
while L:
c, u = heapq.heappop(L)
if dist2[u-1] < c:
continue
for v in d[u-1]:
if dist2[v-1] > c+1:
dist2[v-1] = c+1
heapq.heappush(L, [c+1, v])
L = []
heapq.heapify(L)
heapq.heappush(L, [0, N])
dist3[N-1] = 0
while L:
c, u = heapq.heappop(L)
if dist3[u-1] < c:
continue
for v in d[u-1]:
if dist3[v-1] > c+1:
dist3[v-1] = c+1
heapq.heappush(L, [c+1, v])
ans = min(dist1[N-2] + dist2[N-1] + dist3[0], dist1[N-1] + dist3[N-2] + dist2[0])
print(ans if ans < INF else -1)