[CSA] Round #5 Long Journey

2019年5月14日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] \) の最大値が答えになります。

コード

提出したコード

幅優先探索

// 配列 a に点 s からの最短距離を格納する
void bfs(int a[], int s) {
  init();
  queue<int> q;
  q.push(s);
  a[s] = 0;
  vis[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vector<int> v = G[u];
    for (int i : v) {
      if (vis[i] == 0) {
        q.push(i);
        vis[i] = 1;
        a[i] = a[u] + 1;
      }
    }
  }
}

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