結果
問題 |
No.1995 CHIKA Road
|
ユーザー |
|
提出日時 | 2022-07-01 23:32:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 826 ms / 2,000 ms |
コード長 | 846 bytes |
コンパイル時間 | 700 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 161,064 KB |
最終ジャッジ日時 | 2024-11-26 07:31:51 |
合計ジャッジ時間 | 14,315 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
from collections import defaultdict from heapq import heapify, heappop, heappush n, m = map(int, input().split()) Edge = [] p = set([0, n - 1]) for _ in range(m): a, b = map(int, input().split()) Edge.append((a - 1, b - 1)) p.add(a - 1) p.add(b - 1) sortP = sorted(p) l = len(sortP) idx = 0 H = defaultdict(int) for cp in sortP: H[cp] = idx idx += 1 route = defaultdict(list) for a, b in Edge: route[H[a]].append((H[b], 2 * (b - a) - 1)) for i in range(l - 1): route[i].append((i + 1, 2 * (sortP[i + 1] - sortP[i]))) INF = 10**18 DP = [INF for _ in range(l)] H = [(0, 0)] heapify(H) while H: ccost, cp = heappop(H) if DP[cp] <= ccost: continue DP[cp] = ccost if cp == l - 1: print(DP[l - 1]) break for np, dcost in route[cp]: heappush(H, (ccost + dcost, np))