結果

問題 No.2764 Warp Drive Spacecraft
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0