マツシタのお勉強

ダイクストラ法

Shortest Reach in a Graph in Hacker Rank

問題 n個のノードとm個のエッジによって構成されるグラフが与えられ、スタートノードからその他の全てノードまでの最短距離を求める問題。 www.hackerrank.com 解法 優先度付きキューを用いたダイクストラ法を使って解く 計算量 優先度付きキューに値を追加…

優先度付きキューを用いてダイクストラ法によってたこ焼きを効率よく投げる ARC008 C - THE☆たこ焼き祭り2012

問題 C: THE☆たこ焼き祭り2012 - AtCoder Regular Contest 008 | AtCoder 解法 以下のステップで解くことができる。 ダイクストラ法を用いて始点から各点までの最短時間を算出 始点から離れている点からたこ焼きを配る たこ焼きを受け取った時間が最も遅かっ…

プライオリティキューを用いたダイクストラ法 ~トレジャーハント編 ~

問題 D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder 解法 流れ 滞在する必要のある頂点は1つと考える。滞在する頂点を頂点iとすると、頂点0から最短で頂点iに到達し、できるだけ長く頂点iに滞在し、最短で頂点0に戻る事を考える。頂点iを…

最短経路DAGを作って経路の数え上げをする(動的計画法)

問題 C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder ソースコード一部 ソースコードの全体は最後に添付。 解説 今回の問題では、スタートからゴールまでの最短経路が複数存在し、その経路数を求める問題である。 よって、初めに行うことは…

ダイクストラ法を用いて最短経路で目的地に着く

問題 C: 壁抜け - AtCoder Beginner Contest 020 | AtCoder ソースコード 解説 問題文のxの値を固定し、xが最大となるものを出力する。xが取りうる値の最大値から順番に試し、スタートからゴールまで制限時間内にたどり着けたものを採用する。 まずは全探索…