PAST4O

from 第四回 アルゴリズム実技検定 PAST4O O - 宝箱

• 10^5のレンジ、コスト
• 公式解説
  • 区間で一部を覆う問題に、結果に影響しない区間を付け加えて全部を覆う問題にする
    • スタートやゴールが複数ある最短経路問題で、コスト0の辺を付け加えてスタートやゴールを一つにするのと似ている
  • 区間で覆うコスト最小化→ダイクストラ