結果
問題 |
No.2764 Warp Drive Spacecraft
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:54:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,707 ms / 3,000 ms |
コード長 | 3,701 bytes |
コンパイル時間 | 265 ms |
コンパイル使用メモリ | 82,568 KB |
実行使用メモリ | 253,268 KB |
最終ジャッジ日時 | 2025-03-31 17:56:41 |
合計ジャッジ時間 | 30,785 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
import sys import heapq def dijkstra(adj, start, n): dist = [float('inf')] * (n + 1) dist[start] = 0 heap = [(0, start)] visited = [False] * (n + 1) while heap: d, u = heapq.heappop(heap) if visited[u]: continue visited[u] = True for v, t in adj[u]: if dist[v] > d + t: dist[v] = d + t heapq.heappush(heap, (dist[v], v)) return dist def convex_hull(points): hull = [] for p in points: while len(hull) >= 2: a = hull[-2] b = hull[-1] # Calculate (b - a) × (p - a) cross = (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]) if cross <= 0: hull.pop() else: break hull.append(p) return hull def main(): input = sys.stdin.read().split() ptr = 0 n = int(input[ptr]) ptr += 1 m = int(input[ptr]) ptr += 1 W = list(map(int, input[ptr:ptr+n])) ptr += n adj_forward = [[] for _ in range(n + 1)] adj_reverse = [[] for _ in range(n + 1)] for _ in range(m): u = int(input[ptr]) ptr += 1 v = int(input[ptr]) ptr += 1 t = int(input[ptr]) ptr += 1 adj_forward[u].append( (v, t) ) adj_forward[v].append( (u, t) ) adj_reverse[v].append( (u, t) ) adj_reverse[u].append( (v, t) ) # Compute d0 and d1 d0 = dijkstra(adj_forward, 1, n) d1 = dijkstra(adj_reverse, n, n) # Build convex hull for points (W_j, d1[j]) wd_dict = {} for j in range(1, n+1): w = W[j-1] current_d1 = d1[j] if current_d1 == float('inf'): continue if w not in wd_dict or current_d1 < wd_dict[w]: wd_dict[w] = current_d1 if not wd_dict: # If no points are available, warp is not possible possible_ans = float('inf') else: sorted_ws = sorted(wd_dict.keys()) sorted_points = [ (w, wd_dict[w]) for w in sorted_ws ] hull = convex_hull(sorted_points) # Function to query the minimal a*x + y for current a def query(a): if not hull: return float('inf') left = 0 right = len(hull) - 1 best = 0 while left < right: mid = (left + right) // 2 if a * hull[mid][0] + hull[mid][1] < a * hull[mid+1][0] + hull[mid+1][1]: right = mid else: left = mid + 1 return min( a * hull[i][0] + hull[i][1] for i in range(len(hull)) ) # While the loop above may not always find the best, let's check the entire hull for now (to avoid bugs) # This is for correctness, but may have O(n) time. To optimize, use the binary search approach but carefully. min_val = float('inf') for (x, y) in hull: current = a * x + y if current < min_val: min_val = current return min_val possible_ans = float('inf') for i in range(1, n+1): if d0[i] == float('inf'): continue a = W[i-1] min_warp = query(a) if min_warp == float('inf'): continue total = d0[i] + min_warp if total < possible_ans: possible_ans = total # Compare with the case where we don't use warp ans = min(possible_ans, d0[n]) print(int(ans) if ans != float('inf') else -1) if __name__ == "__main__": main()