結果
問題 | No.2335 Jump |
ユーザー |
|
提出日時 | 2023-06-02 21:27:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 1,222 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 81,884 KB |
実行使用メモリ | 96,620 KB |
最終ジャッジ日時 | 2024-12-28 16:24:49 |
合計ジャッジ時間 | 2,689 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
import sys, time, randomfrom collections import deque, Counter, defaultdictinput = lambda: sys.stdin.readline().rstrip()ii = lambda: int(input())mi = lambda: map(int, input().split())li = lambda: list(mi())inf = 2 ** 63 - 1mod = 998244353def Dijkstra(s, graph):INF = 2 ** 63 - 1import heapqn = len(graph)dist = [INF] * ndist[s] = 0bef = [0] * nbef[s] = shq = [(0, s)]heapq.heapify(hq)while hq:c, now = heapq.heappop(hq)if c > dist[now]:continuefor to, cost in graph[now]:if dist[now] + cost < dist[to]:dist[to] = cost + dist[now]bef[to] = nowheapq.heappush(hq, (dist[to], + to))return dist, befdef DijkstraRest(bef, t):now = tret = []while bef[now] != now:ret.append((bef[now], now))now = bef[now]ret.reverse()return retn = ii()a = li()graph = [[] for _ in range(n)]for i in range(n):if 0 <= i - 1:graph[i].append((i - 1, abs(a[i] - a[i - 1]) - 1))if i + 1 < n:graph[i].append((i + 1, abs(a[i] - a[i + 1]) - 1))d, _ = Dijkstra(0, graph)print(d[n - 1] + a[0] - 1)