夏の遠足ルートに使われる辺はどの辺かをまず求めます。

まず、土地 \(1\) から全ての土地への夏の最短距離をダイクストラ法を用いて求め、土地\(i\) までの最短距離を \(dist_{i}\) をします。

辺 \(i\) について \(dist_{B_{i}}=dist_{A_{i}}+S_{i}\) が成立しているとき、 \(A_{i}\rightarrow B_{i}\) 方向の辺を特別な辺とします。

実はこの特別な辺のみが夏の遠足ルートに含まれます。特別でない辺は使われません。

また、この特別な辺のみを用いて土地 \(1\) から土地 \(N\) まで辿り着いたとき、その総距離は最短距離と等しくなります。

よって、この特別な辺のみを辿って 土地 \(1\) から土地 \(N\) までたどり着くルートの場合の数を求めれば夏の遠足ルートの場合の数を求めることができます。

この場合の数は動的計画法を用いて求めることができます。

具体的には \(dp_{1}=1,dp_{i}=0 (i\neq 1)\) と初期化した後、\(dist_{i}\) が小さい順に、 \(dp_{i}=\sum_{j\rightarrow i \in special\;edge} dp_{j}\) と更新すれば、 \(dp_{N}\) が夏の遠足ルートの場合の数になっています。

以上を用いれば夏の遠足ルートと冬の遠足ルートの場合の数を求めることができます。

ここからどちらの遠足ルートにも含まれるものを引けば問題の答えが求まります。

つまり、夏冬どちらでも特別な辺となっている辺のみを辿って \(1\rightarrow N\) へたどりつける場合の数を引けば良く、これは同様にもとまります。(更新の順番は夏の最短距離の小さい順、冬の最短距離の小さい順のどちらでも良いです。)

計算量はダイクストラ法のパートがネックとなって、 \(O((E+V)\log {V})\) で求められます。

同じ操作を何回もするので、「辺のコストが与えられた時に特別な辺を求める関数」と「特別な辺がわかっているときの、遠足ルートの場合の数を求める関数」を用意すると実装の手間が省けます。

実装例 C++