結果

問題 No.2764 Warp Drive Spacecraft
ユーザー lam6er
提出日時 2025-03-26 15:57:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,092 ms / 3,000 ms
コード長 3,262 bytes
コンパイル時間 227 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 206,564 KB
最終ジャッジ日時 2025-03-26 15:59:43
合計ジャッジ時間 33,666 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq

def dijkstra(adj, start, n):
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    while heap:
        current_dist, u = heapq.heappop(heap)
        if current_dist > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[v] > current_dist + w:
                dist[v] = current_dist + w
                heapq.heappush(heap, (dist[v], v))
    return dist

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 = [[] for _ in range(N)]
    for _ in range(M):
        u = int(input[ptr])-1
        ptr +=1
        v = int(input[ptr])-1
        ptr +=1
        t = int(input[ptr])
        ptr +=1
        adj[u].append( (v, t) )
        adj[v].append( (u, t) )
    
    d1 = dijkstra(adj, 0, N)
    d2 = dijkstra(adj, N-1, N)
    
    points = []
    for j in range(N):
        if d2[j] != float('inf'):
            points.append( (W[j], d2[j]) )
    
    if not points:
        print(d1[N-1] if d1[N-1] != float('inf') else -1)
        return
    
    points.sort()
    filtered = []
    prev_w = None
    for w, d in points:
        if w == prev_w:
            continue
        filtered.append( (w, d) )
        prev_w = w
    
    def build_convex_hull(points):
        stack = []
        for w, d in points:
            while len(stack) >= 2:
                a = stack[-2]
                b = stack[-1]
                val1 = (b[1] - a[1]) * (w - b[0])
                val2 = (d - b[1]) * (b[0] - a[0])
                if val1 >= val2:
                    stack.pop()
                else:
                    break
            stack.append( (w, d) )
        return stack
    
    convex = build_convex_hull(filtered)
    
    def query_convex_hull(convex, x):
        if not convex:
            return float('inf')
        left = 0
        right = len(convex) -1
        res = 0
        while left <= right:
            mid = (left + right) //2
            if mid == len(convex)-1:
                res = mid
                break
            w_mid, d_mid = convex[mid]
            w_next, d_next = convex[mid+1]
            val_mid = w_mid * x + d_mid
            val_next = w_next * x + d_next
            if val_mid <= val_next:
                res = mid
                right = mid -1
            else:
                left = mid +1
        min_val = float('inf')
        for i in range(max(0, res-1), min(len(convex), res+2)):
            w, d = convex[i]
            current_val = w * x + d
            if current_val < min_val:
                min_val = current_val
        return min_val
    
    no_warp = d1[N-1] if d1[N-1] != float('inf') else float('inf')
    warp_min = float('inf')
    for i in range(N):
        if d1[i] == float('inf'):
            continue
        x = W[i]
        min_j_val = query_convex_hull(convex, x)
        if min_j_val == float('inf'):
            continue
        total = d1[i] + min_j_val
        if total < warp_min:
            warp_min = total
    ans = min(no_warp, warp_min)
    print(ans if ans != float('inf') else -1)

if __name__ == '__main__':
    main()
0