読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ダイクストラ

ARC056 B - 駐車場

問題 N 人の人が 1 番目から順に駐車場にやってくる。駐車場は N 個の駐車スペースが無向辺で結ばれたグラフで表され、入り口は頂点 S である。i 番目の人は i 番目の駐車スペースに車を停めるか、停められないならば停めずに帰る。 駐車できる人の番号をす…

ABC022 C - Blue Bird

想定解と違うっぽかったので書いておきます。(ダイクストラで解いた) 問題 abc022.contest.atcoder.jp グラフが与えられるので、地点1から出発し地点1に戻ってくるような閉路が存在するとき、その最小の重みの和を求めよ。そのような閉路が存在しないとき…

ダイクストラ法とその例題

ダイクストラ法とその例題についてまとめておきます。 例題はワーシャルフロイドのやつ使いまわしです(ダイクストラ向きのは二分探索とか絡んで難しいので……) ダイクストラ法とは? ダイクストラ法(Dijkstra's algorithm)は、グラフのある点から各点までの…