D - Super Takahashi Bros.

キーワード

解説

ステージを頂点、ステージ間の移動を辺、ステージのクリア時間を重みとすると、全体は重み付き有向グラフとして考えることができる。

ステージ $1$ からはじめて、ステージ　 $N$ が遊べるまでの最短時間は、ステージ $1$ からステージ $N$ までの最短経路を求めることで求めることができる。

従って、ダイクストラ法を用いればよい。

計算量は線形探索を行うと $\mathrm{O}(N^2)$ だが、heap を使うことで $\mathrm{O}(N\log{N})$ で求めることができる。

提出コード

import heapq
 
n = int(input())
 
g = [[] for _ in range(n + 1)]
 
for i in range(1, n):
    a, b, x = map(int, input().split())
    g[i].append((i + 1, a))
    g[i].append((x, b))
 
D = [float("inf")] * (n + 1)
D[1] = 0
 
q = [(0, 1)]
 
while q:
    d, to = heapq.heappop(q)
 
    if D[to] < d:
        continue
 
    for u, c in g[to]:
        if D[to] + c < D[u]:
            D[u] = D[to] + c
            heapq.heappush(q, (D[u], u))
 
print(D[-1])

func main() {
    n := readInt()
	g := simple.NewWeightedDirectedGraph(0, math.Inf(1))
	for i := 1; i <= n; i++ {
        node := simple.Node(i)
		g.AddNode(node)
	}
	for i := 1; i <= n-1; i++ {
        var a, b, x int
		scanIntVariables(&a, &b, &x)
		g.SetWeightedEdge(simple.WeightedEdge{F: simple.Node(i), T: simple.Node(i + 1), W: float64(a)})
		if i == x {
            continue
		}
		g.SetWeightedEdge(simple.WeightedEdge{F: simple.Node(i), T: simple.Node(x), W: float64(b)})
	}
 
	shortest := path.DijkstraAllFrom(simple.Node(1), g)
	_, w, _ := shortest.To(int64(n))
	writeLine(int(w))
}

gonum/graphを使うと WA　になる。要検証。

C - Divide and Divide 341