結果
| 問題 | No.2569 はじめてのおつかいHard |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-12 11:51:21 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,365 ms / 2,000 ms |
| + 666µs | |
| コード長 | 1,571 bytes |
| 記録 | |
| コンパイル時間 | 111 ms |
| コンパイル使用メモリ | 64,392 KB |
| 実行使用メモリ | 140,752 KB |
| 最終ジャッジ日時 | 2026-11-12 11:51:38 |
| 合計ジャッジ時間 | 13,010 ms |
|
ジャッジサーバーID (参考情報) |
judge3_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 11 |
ソースコード
import heapq
N, M = (int(x) for x in input().split())
d = [[] for i in range(N)]
rd = [[] for i in range(N)]
for i in range(M):
u, v, t = (int(x) for x in input().split())
d[u-1].append([v, t])
rd[v-1].append([u, t])
INF = 10**18
dist1, dist2 = [INF]*N, [INF]*N
L = []
heapq.heapify(L)
heapq.heappush(L, [0, N-1])
dist1[N-1-1] = 0
while L:
c, u = heapq.heappop(L)
if dist1[u-1] < c:
continue
for v, t in d[u-1]:
if dist1[v-1] > c+t:
dist1[v-1] = c+t
heapq.heappush(L, [c+t, v])
L = []
heapq.heapify(L)
heapq.heappush(L, [0, N])
dist2[N-1] = 0
while L:
c, u = heapq.heappop(L)
if dist2[u-1] < c:
continue
for v, t in d[u-1]:
if dist2[v-1] > c+t:
dist2[v-1] = c+t
heapq.heappush(L, [c+t, v])
rdist1, rdist2 = [INF]*N, [INF]*N
L = []
heapq.heapify(L)
heapq.heappush(L, [0, N-1])
rdist1[N-1-1] = 0
while L:
c, u = heapq.heappop(L)
if rdist1[u-1] < c:
continue
for v, t in rd[u-1]:
if rdist1[v-1] > c+t:
rdist1[v-1] = c+t
heapq.heappush(L, [c+t, v])
L = []
heapq.heapify(L)
heapq.heappush(L, [0, N])
rdist2[N-1] = 0
while L:
c, u = heapq.heappop(L)
if rdist2[u-1] < c:
continue
for v, t in rd[u-1]:
if rdist2[v-1] > c+t:
rdist2[v-1] = c+t
heapq.heappush(L, [c+t, v])
ans = []
for i in range(N-2):
res = min(rdist1[i] + dist1[N-1] + dist2[i], rdist2[i] + dist2[N-2] + dist1[i])
ans.append(res if res < INF else -1)
for i in ans:
print(i)