[CSA] Round #5 Long Journey

Long Journey

https://csacademy.com/contest/beta-round-5/task/long_journey/statement/

始点が同じで終点が異なる二つの最短経路において、同じ辺を通る数の最大値を答える問題です。

考え方

解き方が分からなかったので解説を読みました。

ある点からすべての到達可能な点の最短距離は、幅優先探索などで求めることができます。これを点 \(S, A, B \) について求めます。ここで、\( d_{i}[j]\) を 点 \(i\) から 点 \(j\) への最短距離とします。

\( (S, A) \) の最短経路上では、

\[d_{S}[A] = d_{S}[i] + d_{A}[i]\]

が成り立ちます。どうようにして、\( (S, B) \) の最短経路においても同じことが言えます。これを利用して、

\[d_{S}[A] = d_{S}[i] + d_{A}[i] \ \& \ d_{S}[B] = d_{S}[i] + d_{B}[i]\]

を満たす最大の \( d_{S}[i] \) を求めれば良いです。

ソースコード

感想

解説の解き方は思いつきませんでした。こういうやり方があるのかとためになりました。

隣接リストの実装が悪くTLEとなってしまい、他の提出コードを参考にして書き換えました。公式の解説の隣接リストの表現が高速のようですが、いまいち分かりませんでした。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする