C: ウサギとカメ | AtCoder Regular Contest 025

ダイクストラ法っぽいことをする。

(時間、誰(ウサギ、カメ), 場所, 始点)

のようなタプルを優先順位付きキューに入れていく。

まず、

場所＝始点、時間0で両者をすべての頂点からスタートさせる。

以降、各始点からの最短経路だけを考える。

今いる場所と始点が異なるとき、カメはその地点のカウンタを1個増やす。

今いる場所と始点が異なるとき、ウサギはカメのカウンタを数える。つまり、先に今いる場所に来た経路を数える。ただし、カメも同じスタート地点から来ている経路だけは取り除く。

全体で

O(NMlog(M))

の時間でなんとか間に合う。