結果

問題 No.2764 Warp Drive Spacecraft
コンテスト
ユーザー detteiuu
提出日時 2026-07-22 02:22:12
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,377 ms / 3,000 ms
+ 372µs
コード長 1,860 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 232 ms
コンパイル使用メモリ 95,976 KB
実行使用メモリ 173,536 KB
最終ジャッジ日時 2026-07-22 02:22:38
合計ジャッジ時間 26,058 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from sys import stdin
input = stdin.readline
from heapq import heappush, heappop
from collections import deque

class Convex_Hull_Trick:
    def __init__(self):
        self.que = deque()

    def check(self, f1, f2, f3):
        return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])
    
    def f(self, f1, x):
        return f1[0]*x + f1[1]
    
    # add f_i(x) = a*x + b
    def add_line(self, a, b):
        f1 = (a, b)
        while len(self.que) >= 2 and self.check(self.que[-2], self.que[-1], f1):
            self.que.pop()
        self.que.append(f1)

    # min f_i(x)
    def query(self, x):
        while len(self.que) >= 2 and self.f(self.que[0], x) >= self.f(self.que[1], x):
            self.que.popleft()
        return self.f(self.que[0], x)

INF = 1<<60

N, M = map(int, input().split())
W = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(M):
    u, v, c = map(int, input().split())
    u, v = u-1, v-1
    G[u].append((v, c))
    G[v].append((u, c))

def dijkstra(dist):
    visited = [False]*N
    que = []
    for i in range(N):
        if dist[i] != INF:
            heappush(que, (dist[i], i))
    while que:
        d, now = heappop(que)
        if visited[now]:
            continue
        visited[now] = True
        for next, weight in G[now]:
            if dist[now]+weight < dist[next]:
                dist[next] = dist[now]+weight
                heappush(que, (dist[next], next))
    return dist

dist1 = [INF]*N
dist1[0] = 0
dist1 = dijkstra(dist1)
ans = dist1[-1]
dist1 = sorted([(W[i], dist1[i]) for i in range(N)], reverse=True)

CHT = Convex_Hull_Trick()
for w, d in dist1:
    CHT.add_line(w, d)

IDX = sorted(range(N), key=lambda x:W[x])
dist2 = [INF]*N
for idx in IDX:
    dist2[idx] = CHT.query(W[idx])

dist2 = dijkstra(dist2)
ans = min(ans, dist2[-1])

print(ans)
0