きままにものづくりスマートフォン用の表示で見るきままにものづくり日々の気付いたことなんかを書いてます。この広告は、90日以上更新していないブログに表示しています。2014-12-13SRM624Div1Medium問題ノード数N、エッジ数Eの無向グラフが与えられる。それぞれのノードには1~Nまで番号が振られている。各エッジはコストを持っている。コストは0を取ることが可能である。1からNまでの最短となるパスの数を求めよ。無限にある場合は-1とする。解法1まず全点対最短路を求める。なってしまうため、Dijkstraを全点に対して行う。全点対最短路distを用いることで、エッジeが最短路に含まれるかを以下の式で判断できる。エッジの始点をs、終点をt、コストをcとする。上の式を用いて最短路にコスト0のエッジが含まれるかを調べる。次に、深さ優先探索を用いて最短路のパスの数を計算する。そのままでは、計算量が大きくなるのでメモ化をする。計算量1全点対最短路:深さ優先探索:コード1解法2全点対最短路を用いなくても1からの単一始点最短路distとNからの単一始点最短路rdistがあれば、以下の式でコスト0のエッジが含まれるかを調べることができる。エッジの始点をs、終点をt、コストをcとする。rdistと動的計画法を用いてパスの数を計算する。ある頂点からNまでの最短路の数を計算する。これをNから近い順に行っていく。(1)月別アーカイブはてなブログをはじめよう!even_ekoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。