結果

問題 No.2764 Warp Drive Spacecraft
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:56:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,758 ms / 3,000 ms
コード長 3,074 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 177,272 KB
最終ジャッジ日時 2025-03-20 18:58:13
合計ジャッジ時間 33,931 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

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