AOJ2249: Road Construction

アルゴリズム/最短経路 データ構造/グラフ 競技プログラミング 競技プログラミング/AOJ

Road Construction | Aizu Online Judge

解き方

  • captalを始点としてdijkstraして、その後経路復元
    • 経路復元のための情報において、条件を満たす辺のなかでコスト最小のものを保存するようにする
  • 多分、priority_queueを使ったdijkstraじゃないとTLEすると思う

ハマったところ

github.com