As Soon As Possible

想定解1 $O((M + N) \log M \log N)$ ダイクストラ法

前処理として、バスを $(A, B)$ ごとにまとめ、それぞれを $(S, T)$ の昇順でソートし、 $T$ について後ろからの累積 $\min$ をとります。

ダイクストラ法の遷移の際に、現在の時刻よりも $S$ が大きい最小のバスを二分探索します。

提出

想定解2 $O(M \log M)$ ダイクストラ法（みさわさんより）

ダイクストラ法の遷移の際に、今見ているバスが乗れるバスかを判定します。

提出

想定解3 $O(M \log M)$ DP（H20さんより）

バスを $S$ の昇順でソートします。

街 $1$ の到着時刻を $0$ 、それ以外の街の到着時刻を $\infty$ で初期化します。

それぞれのバスについて、街 $A$ の到着時刻が $S$ 以下のとき、街 $B$ の到着時刻を $T$ 以下にします。

提出