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から近い順に行っていく。