公開されている「典型アルゴリズム問題集」のD問題をC++で解いてみました。リンク先をご覧ください。グラフの始点から、すべての終点への最小移動距離を求めます。0以上の整数で与えられます。algorithm)が使えます。基本的な考え方は以下です。頂点とコストを組にして、キューを使って処理する。コストが小さい順番に処理する。このため、優先度付きキューを使う場合が多くなります。algorithm)を使う必要があります。この記事では紹介しません。重み付きグラフの定番コードと考えることができます。上でも述べましたが、優先度付きキューを使います(30行目)。キューの初期値として、始点(頂点0)を格納します(31、32行目)。キューが空になるまで、コストが小さい順に処理します(34ー45行目)。37行目の確認が抜けていると、時間がかかる場合があります。dist[n-1]が求める解答になります。以下が、C++プログラムとなります。0;}AC(Accepted=正しいプログラム)と判定されました。最後に何回か紹介したダイクストラ法の復習ができました。ある意味貪欲法ですが、応用範囲が広いアルゴリズムだと考えています。この問題集は、わたくしには、ちょうど良い難易度でした。引き続き解答案を紹介していきます。コメントをキャンセルメールアドレスが公開されることはありません。付いている欄は必須項目です上に表示された文字を入力してください。Contest)記事一覧ソフトウェア技術者アナダパンチ組込み製品の開発に従事しているソフトウェア技術者です。仕事でソフトウェア開発に従事しながら、趣味でもプログラミングを楽しんでいます。