きままにものづくり

日々の気付いたことなんかを書いてます。

SRM624Div1Medium

問題

ノード数N、エッジ数Eの無向グラフが与えられる。それぞれのノードには1~Nまで番号が振られている。各エッジはコストを持っている。コストは0を取ることが可能である。1からNまでの最短となるパスの数を求めよ。無限にある場合は-1とする。

解法1

まず全点対最短路を求める。Floy-WarshallではO(N^3)となってしまうため、Dijkstraを全点に対して行う。この時の計算量は O(NE logN)となる。全点対最短路distを用いることで、エッジeが最短路に含まれるかを以下の式で判断できる。ただし、エッジの始点をs、終点をt、コストをcとする。
 dist[1][s] + c + dist[t][N] = dist[1][N]
上の式を用いて最短路にコスト0のエッジが含まれるかを調べる。次に、深さ優先探索を用いて最短路のパスの数を計算する。そのままでは、計算量が大きくなるのでメモ化をする。

計算量1

全点対最短路: O(NE log N)
深さ優先探索: O(N)

コード1


解法2

全点対最短路を用いなくても1からの単一始点最短路distとNからの単一始点最短路rdistがあれば、以下の式でコスト0のエッジが含まれるかを調べることができる。ただし、エッジの始点をs、終点をt、コストをcとする。
 dist[s] + rdist[t] = dist[N] \land c = 0
rdistと動的計画法を用いてパスの数を計算する。ある頂点からNまでの最短路の数を計算する。これをNから近い順に行っていく。

コード2

広告を非表示にする