結果
問題 |
No.1995 CHIKA Road
|
ユーザー |
|
提出日時 | 2022-07-01 23:27:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 846 ms / 2,000 ms |
コード長 | 895 bytes |
コンパイル時間 | 233 ms |
コンパイル使用メモリ | 82,044 KB |
実行使用メモリ | 155,132 KB |
最終ジャッジ日時 | 2024-11-26 07:24:28 |
合計ジャッジ時間 | 13,619 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
import sys from collections import defaultdict, deque from heapq import heapify, heappush, heappop input = lambda: sys.stdin.readline().rstrip() inf = float('inf') def dijkstra(G: list, s: int) -> list: "Return dist from s. / O(|E|log|V|)" dist = defaultdict(lambda: inf) dist[s] = 0 hq = [(0, s)] while hq: d, v = heappop(hq) if dist[v] < d: continue for x,c in G[v]: if dist[x] > d + c: dist[x] = d + c heappush(hq, (d+c, x)) return dist # ----------------------- # n, m = map(int, input().split()) G = defaultdict(list) E = [] for _ in range(m): a, b = map(int, input().split()) G[a-1].append((b-1, 2*b-2*a-1)) E.append(a-1) E.append(b-1) E.append(0) E.append(n-1) E.sort() for i in range(len(E)-1): now, nxt = E[i], E[i+1] dist = (E[i+1] - E[i]) * 2 G[now].append((nxt, dist)) dist = dijkstra(G, 0) print(dist[n-1])