アルゴリズム/最短経路

ARC083 D: Restoring Road Network

D - Restoring Road Network 解き方 これまでに追加した辺のコストの合計と、その辺による各都市間の最短距離(d[i][j])を保持、更新する 距離が小さい方から順に考えていく。 町i, j間の最短距離がcの時、 もし、d[i][j] == cならば、もう辺を追加する必要は…

AOJ2200: Mr. Rito Post Office

Mr. Rito Post Office | Aizu Online Judge 解き方 からへの行き方は次の2通り 陸路で行く 船のあるところまで陸路で行き、船で適当なところまで行き、再度陸路 前計算として、陸路での最短距離、海路での最短距離をWarshall Floydで求めておく dp[i][j] = …

AOJ2249: Road Construction

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

AOJ 0588: Cheese

チーズ | Aizu Online Judge 蟻本の練習問題に挙げられていたので練習 解き方 幅優先探索 N=9なので,Nそれぞれに対して幅優先探索しても,9*10^6程度のループ回数で済む ハマった所 最初,N=9を見逃して効率良い幅優先を考えていた コンテストだったらただ…