結果
問題 |
No.2764 Warp Drive Spacecraft
|
ユーザー |
![]() |
提出日時 | 2025-03-20 21:12:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,064 ms / 3,000 ms |
コード長 | 3,074 bytes |
コンパイル時間 | 292 ms |
コンパイル使用メモリ | 82,412 KB |
実行使用メモリ | 177,280 KB |
最終ジャッジ日時 | 2025-03-20 21:14:10 |
合計ジャッジ時間 | 26,004 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
import heapq class LichaoNode: def __init__(self, l, r): self.l = l self.r = r self.a = None # line's slope (Wj) self.b = None # line's intercept (Dn[j]) self.left = None self.right = None def update(self, a_new, b_new): if self.a is None: self.a = a_new self.b = b_new return mid = (self.l + self.r) // 2 current_val = self.a * mid + self.b new_val = a_new * mid + b_new if new_val < current_val: # Swap the lines self.a, a_new = a_new, self.a self.b, b_new = b_new, self.b # Check left child left_new = a_new * self.l + b_new left_current = self.a * self.l + self.b if left_new < left_current: if self.left is None: self.left = LichaoNode(self.l, mid) self.left.update(a_new, b_new) # Check right child right_new = a_new * self.r + b_new right_current = self.a * self.r + self.b if right_new < right_current: if self.right is None: self.right = LichaoNode(mid + 1, self.r) self.right.update(a_new, b_new) def query(self, x): res = float('inf') if self.a is not None: res = self.a * x + self.b mid = (self.l + self.r) // 2 if x <= mid and self.left is not None: left_res = self.left.query(x) res = min(res, left_res) elif x > mid and self.right is not None: right_res = self.right.query(x) res = min(res, right_res) return res def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]) M = int(data[idx+1]) idx += 2 W = list(map(int, data[idx:idx+N])) idx += N W = [0] + W # 1-based adj = [[] for _ in range(N+1)] for _ in range(M): u = int(data[idx]) v = int(data[idx+1]) t = int(data[idx+2]) adj[u].append( (v, t) ) adj[v].append( (u, t) ) idx += 3 INF = 1 << 60 def dijkstra(start): dist = [INF] * (N + 1) dist[start] = 0 heap = [ (0, start) ] heapq.heapify(heap) while heap: d, u = heapq.heappop(heap) if d > dist[u]: continue for v, t in adj[u]: if dist[v] > d + t: dist[v] = d + t heapq.heappush(heap, (dist[v], v)) return dist d1 = dijkstra(1) dn = dijkstra(N) root = LichaoNode(0, 1 << 60) lines_exist = False for j in range(1, N+1): if dn[j] < INF: root.update(W[j], dn[j]) lines_exist = True warp_min = INF if lines_exist: for i in range(1, N+1): if d1[i] < INF: min_val = root.query(W[i]) warp_min = min(warp_min, d1[i] + min_val) ans = min(d1[N], warp_min) print(ans) if __name__ == "__main__": main()