結果

問題 No.2764 Warp Drive Spacecraft
コンテスト
ユーザー 回転
提出日時 2025-11-14 16:08:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,174 ms / 3,000 ms
コード長 3,307 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 212,340 KB
最終ジャッジ日時 2025-11-14 16:09:52
合計ジャッジ時間 40,805 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import List, Tuple
from bisect import bisect_left

class LiChaoTree:
    def __init__(self, variables: List[int]) -> None:
        if any(not a < b for a, b in zip(variables, variables[1:])):
            raise ValueError('variables must be sorted')
        self.inf = (1 << 63) - 1
        self.n = len(variables)
        self.size = 1 << (self.n - 1).bit_length()
        self.variables = variables + [self.inf] * (self.size - self.n)
        self.a = [0] * (2 * self.size)
        self.b = [self.inf] * (2 * self.size)

    def __findpos(self, x: int) -> Tuple[int, bool]:
        p = bisect_left(self.variables, x)
        if p >= self.n or self.variables[p] != x: return p, False
        return p, True

    def __add(self, a: int, b: int, idx: int, lpos: int, rpos: int) -> None:
        while True:
            mpos = (lpos + rpos) >> 1
            lx = self.variables[lpos]
            mx = self.variables[mpos]
            rx = self.variables[rpos - 1]
            ai, bi = self.a[idx], self.b[idx]
            lu = a * lx + b < ai * lx + bi
            mu = a * mx + b < ai * mx + bi
            ru = a * rx + b < ai * rx + bi
            if lu and ru:
                self.a[idx], self.b[idx] = a, b
                return
            if not lu and not ru:
                return
            if mu:
                self.a[idx], self.b[idx], a, b = a, b, self.a[idx], self.b[idx]
            if lu != mu:
                rpos = mpos
                idx = 2 * idx
            else:
                lpos = mpos
                idx = 2 * idx + 1

    def add_line(self, a: int, b: int) -> None:
        self.__add(a, b, 1, 0, self.size)

    def add_segment(self, a: int, b: int, l: int, r: int) -> None:
        lpos, _ = self.__findpos(l)
        rpos, _ = self.__findpos(r)
        lidx = lpos + self.size
        ridx = rpos + self.size
        sz = 1
        while lidx < ridx:
            if lidx & 1:
                self.__add(a, b, lidx, lpos, lpos + sz)
                lidx += 1
                lpos += sz
            if ridx & 1:
                ridx -= 1
                self.__add(a, b, ridx, rpos - sz, rpos)
                rpos -= sz
            lidx >>= 1
            ridx >>= 1
            sz <<= 1

    def get_min(self, x: int) -> int:
        p, f = self.__findpos(x)
        if not f: raise ValueError('x is not in variables')
        idx = p + self.size
        res = self.a[idx] * x + self.b[idx]
        while idx > 1:
            idx >>= 1
            res = min(res, self.a[idx] * x + self.b[idx])
        return res

import heapq
N,M = list(map(int,input().split()))
W = list(map(int,input().split()))
edge = [[] for _ in range(N)]
for _ in range(M):
    u,v,t = list(map(int,input().split()))
    u -= 1;v -= 1
    edge[u].append((v,t))
    edge[v].append((u,t))

INF = 10**18
def f(start):
    dist = [INF for _ in range(N)]
    q = [(0,start)]
    while(q):
        v,now = heapq.heappop(q)

        if(dist[now] <= v):continue
        dist[now] = v
        
        for i,w in edge[now]:
            heapq.heappush(q,(v+w,i))
    
    return dist

start = f(0)
goal = f(N-1)

ans = start[N-1]
lct = LiChaoTree(sorted(set(W)))
for i in range(N):
    lct.add_line(W[i], goal[i])

for i in range(N):
    ans = min(ans, start[i] + lct.get_min(W[i]))

print(ans)
0