🚲
[ABC137 E] Coins Respawn
START〜GOAL間にない負閉路は無視する問題。
例1で問題を理解する
- 辺を通るごとに 1 分かかる
- 全体で T 分かかる
- 最後に T 分 × P(10) 枚のコインを支払う
のルールなので二つのルートを計算すると、
| ルート | 計算 | 残高 |
|---|---|---|
| 1-2-3 | 20 + 30 - 2 * 10 | 30 |
| 1-3 | 45 - 1 * 10 | 35 |
となるが、あらかじめ辺のコストから P を引いておくと、
| ルート | 計算 | 残高 |
|---|---|---|
| 1-2-3 | 10 + 20 | 30 |
| 1-3 | 35 | 35 |
計算が簡単になる。
またコストがマイナスになるかもしれないのでベルマン-フォード法を用いる。
注意点
START〜GOAL 間にない負閉路は無視すること。
コード (AC)
N, M, P = gets.split.collect(&:to_i) # => [3, 3, 10]
Edges = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2, 20], [2, 3, 30], [1, 3, 45]]
START = 1
GOAL = N
Edges = Edges.collect { |from, to, score| [from, to, score - P] } # => [[1, 2, 10], [2, 3, 20], [1, 3, 35]]
d = Hash.new(-Float::INFINITY) # distance
d[START] = 0
(N * 2).pred.times do |i|
updated = false
Edges.each do |from, to, score|
v = d[from] + score
if v > d[to]
if i == N.pred
v = Float::INFINITY # 関連する経路だけに(本当の値ではなく)∞を伝搬する
end
d[to] = v
updated = true
end
end
unless updated
break
end
end
p d[GOAL].infinite? ? -1 : [d[GOAL], 0].max # => 35
負閉路を検出したらN周かけて∞を伝搬させる。
関係ない経路を除去する解き方
コード (AC)
N, M, P = gets.split.collect(&:to_i) # => [3, 3, 10]
Edges = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2, 20], [2, 3, 30], [1, 3, 45]]
START = 1 # => 1
GOAL = N # => 3
Edges = Edges.collect { |from, to, score| [from, to, score - P] } # => [[1, 2, 10], [2, 3, 20], [1, 3, 35]]
# スタートとゴールからたどりつけない辺を除外するか？
if true
def dfs(edges, from, visited = {})
unless visited[from]
visited[from] = true
edges[from].each { |to| dfs(edges, to, visited) }
end
visited
end
# スタートから辿りつけない辺を除外する
if true
start_to_goal = Hash.new { |h, k| h[k] = [] }
Edges.each { |a, b| start_to_goal[a] << b }
visited = dfs(start_to_goal, START) # => {1=>true, 2=>true, 3=>true}
Edges = Edges.find_all { |from, to, _| visited[from] && visited[to] }
end
# ゴールから辿りつけない辺を除外する
if true
goal_to_start = Hash.new { |h, k| h[k] = [] }
Edges.each { |a, b| goal_to_start[b] << a }
visited = dfs(goal_to_start, GOAL) # => {3=>true, 2=>true, 1=>true}
Edges = Edges.find_all { |from, to, _| visited[from] && visited[to] }
end
end
d = Hash.new(-Float::INFINITY) # distance
d[START] = 0
success = catch(:abort) do
N.times do |i|
updated = false
Edges.each do |from, to, score|
v = d[from] + score
if v > d[to]
if i == N.pred
throw :abort
end
d[to] = v
updated = true
end
end
unless updated
break
end
end
true
end
p success ? [0, d[GOAL]].max : -1 # => 35
事前の準備が大変だが負閉路検出時には即終了して問題ない。
類題
Discussion