目的地にその日のうちに辿り着ける場合のみを考えます。(公式解説を参照) また、それぞれの道について、代わりに有向の道が \(2\) つあるものとします。

ある都市 \(\mathrm{origin}\) を起点とする経路について考えます。出発時刻 \(t\) を \(S\) から \(0\) までだんだん早めていくと、それぞれの道 \(e\) について、ある時刻 \(f(\mathrm{origin}, e)\) であって、 \(t \leq f(\mathrm{origin}, e)\) であれば道 \(e\) が最短経路に使われうる、つまり \(e\) の始点に時刻 \(C_e - L_e\) までに到達できるような \(f(\mathrm{origin}, e)\) が存在するはずです。この条件が \(t\) について単調なので、つまり出発時刻を早めていくとだんだん使える道が増えていくということになります。

これを素直に実装すると、結局 \(N\) 個のあり得る起点それぞれについて、辺を \(1, 2, \dots ,M\) 本と増やしながら起点からの最短経路を更新することになり、時間計算量が \(O(N^3M)\) になります。距離が動的に更新されるので、辺を増やす操作をするたびに、次に増やすべき辺 (一番早く、新しく使えるようになる辺) を全探索する感じになりますが、これはボトルネックにはなりません。

ダイクストラの操作をするたびに時間計算量 \(O(N^2)\) かけて最短距離を更新しているのがボトルネックです。これを解消するために、全ての始点について並列に、出発時刻を早めながら距離を更新することにします。

グラフにある辺が増えたら最短経路がどう変わるかを考えると、その辺を使った先の距離しか変わらないです。すると、ある起点 \(f\) についてのグラフに辺 \(e\) を増やしたとき、 \(f\) を出発して \(e\) を用いた後、 \(e\) の終点からの最短経路のみを更新すれば良いことになります。これは、より遅い時刻に \(B_e\) を起点として出発する最短経路として、過去に求めたことがあるので、そのデータを流用できます。これで計算量が \(O(N^2M)\) になって、満点が取れます。定数倍がよいようです。提出 (fastest)