[CSA] Round #5 Long Journey

2019年5月15日

問題

問題の意図

頂点数が \( N \) 個で辺の数が \( M \) 本の無向グラフが与えられます。始点 \( S \) から終点 \(A, B \) への最短経路において、同じ辺を通る長さの最大値を答えます。また、辺の重みは \( 1 \) です。

方針

ある点から別の点への最短距離

ある点からすべての到達可能な点への最短距離は、幅優先探索などで求めることができます。辺の重みは \( 1 \) なので、迷路の探索をイメージすると分かりやすいかもしれません。

最短距離の性質

\( d_i [j] \) を 点 \( i \) から点 \( j \) への最短距離とします。パス \( S – A \) の最短経路において、点 \( i \) が最短経路上に存在するとき次の式が成立します。

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

これは、\( S-A \) の最短距離は、点 \( i \) を経由して分解できるということです。同様にして \( S – B \) についても同じことが成り立ちます。このような性質を利用して次のことを調べます。

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

上記を満たす点 \( i \) が存在するとき、\( d_{S}[i] \) の最大値が答えになります。

コード

提出したコード

幅優先探索

\( vis \) という配列で訪れた点を管理します。