六月

体力と金額の両方を考えないといけないですが $t_i=2$ の金額コストを適当に大きな数（例えば$10^{10}$）と定義すると金額だけ考えれば良くなります。 $t_i=1$ のときの金額コストが $t_i=2$ の金額コストより十分に小さいとき、金額についての最短経路と $t_i=1$ の道を優先して移動したときの経路が一致します。 したがって、金額の最短経路をダイクストラ法などで処理したあと $t_i=2$ の金額合計を無視するために答えを $t_i=2$ の金額で割った余りで出力すれば良いです。 計算量は$O(K(N+M) \log N)$となります。