PAST4O
from
第四回 アルゴリズム実技検定
PAST4O
O - 宝箱
10^5のレンジ、コスト
公式解説
区間で一部を覆う問題に、結果に影響しない区間を付け加えて全部を覆う問題にする
スタートやゴールが複数ある最短経路問題で、コスト0の辺を付け加えてスタートや
ゴールを一つにする
のと似ている
区間で覆うコスト最小化→ダイクストラ