解説

普通に最短距離を求める場合、 $O(Q (M + N \log N))$ となり間に合いません。

そこで、帰りの時間は普通にダイクストラ法を使い、行きは逆向きに辺を張ったグラフに対してダイクストラ法を使うことで、 $O(M + N \log N + Q)$ で求めることができました（想定解）。