ABC340 D - Super Takahashi Bros.

atcoder.jp

問題

• TVゲームをしてるよ
• 今は始めたばかりなので、ステージ1しか遊べないよ
• ステージ$i$を$A_{i}$秒かけてクリアすると、ステージ$i+1$が遊べるよ
• ステージ$i$を$B_{i}$秒かけてクリアすると、ステージ$X_i$が遊べるよ
• ステージ$N$が遊べるようになるのは、最短で何秒後？

成約

• $2 \leq N \leq 2\times 10^{5}$
• $1 \leq A_i, B_i \leq 10^{9}$
• $1 \leq X_{i} \leq N$

思考

• ステージを頂点にしたグラフとして見えるね
• ステージ遷移が辺で、ステージにかける時間がコスト
• ダイクストラそのまま！

コード

import heapq

N = int(input())
edge_L = [[] for _ in range(N)]

for i in range(N-1):
    A,B,X = map(int,input().split())
    edge_L[i].append((A,i+1))
    edge_L[i].append((B,X-1))


def dijkstra(edges,start,goal):

    hq = []
    inf = 10**18
    ret = [inf]*N
    hq.append((0,start))
    ret[start] = 0

    while hq:
        dist,now = heapq.heappop(hq)
        if ret[now] < dist:continue
        for cost,to in edges[now]:
            if ret[to] <= dist + cost:continue
            ret[to] = dist + cost
            heapq.heappush(hq,(ret[to],to))

    return ret[goal]


print(dijkstra(edge_L,0,N-1))