【AtCoder】ABC 429 E - Hit and Away

E - Hit and Away

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1313 / NoviSteps: 1D / 配点: 450 点

問題概要

$N$ 頂点 $M$ 辺の単純連結無向グラフ $G$ が与えられる。 $G$ の頂点および辺はそれぞれ頂点 $1,2,\ldots,N$、辺 $1,2,\ldots,M$ と番号づけられており、辺 $i$ は頂点 $U_i$ と頂点 $V_i$ を結んでいる。 辺で結ばれている頂点の間は双方向に時間 $1$ で移動することができる。

また、各頂点は安全か危険かのどちらかであり、その状態はSとDのみからなる長さ $N$ の文字列 $S$ によって与えられる。 ここで、安全な頂点が $2$ つ以上、危険な頂点が $1$ つ以上あることが保証される。

危険な頂点 $v$ それぞれについて、次の値を求めよ。

• ある安全な頂点から出発し、$v$ を経由して出発した頂点と異なる安全な頂点へ移動するのにかかる時間としてあり得る最小値

制約

• $3\leq N\leq 2\times 10^5$
• $N-1\leq M\leq 2\times 10^5$
• $N,M,U_i,V_i$ はすべて整数

考察

$M, N$ の制約が大きいので、全ての安全な頂点あるいは危険な頂点から BFS を行うようなやり方では、 計算量が $O(\min(V_S, V_D) \times (N + M)) \rightarrow O(N(N + M))$ となってしまい、間に合わない($V_S, V_D$ はそれぞれ安全な頂点と危険な頂点の個数)。

そこで、危険な頂点それぞれに対して、安全な頂点のうち近いものから 2 点とそこまでの距離を求めることを考える。

今回は全ての辺の重みが $1$ で等しいので、始点を全ての安全な頂点とする多始点 BFS を行うことができる。

ただし、 BFS の探索条件を工夫する必要がある。

ここでは近いものから 2 点までの情報を知りたいので、「次に探索する頂点に異なる 2 点から到達したか否か」を管理するように変更する。 具体的には、以下のようになる。

現在の頂点 $u$ までの経路の始点を $s$ 、ここまでの距離を $d_u$ として、状態 $(s, u, d_u)$ を queue から取り出したとする。

また、以下の 2 つの二次元配列を定義する。

$u$ の各隣接頂点 $v$ に対して、

• $v$ がまだ一度も探索されていない場合 $(\mathrm{from}_{v, 0} = -1)$ :

  • $s \rightarrow u \rightarrow v$ の経路が $v$ までの最短経路である。
  • $\mathrm{from}_{v, 0} = s, \, \mathrm{dist}_{v, 0} = d_u + 1$ とする。
  • 新たに状態 $(s, v, d_u + 1)$ を queue に格納する。

• $v$ への二番目の経路が未探索かつ、始点が最短経路のものと異なる場合 $(\mathrm{from}_{v, 0} \neq s \wedge \mathrm{from}_{v, 1} = -1)$ :

  • $s \rightarrow u \rightarrow v$ の経路が $v$ までの二番目に短い経路である。
  • $\mathrm{from}_{v, 1} = s, \, \mathrm{dist}_{v, 1} = d_u + 1$ とする。
  • 新たに状態 $(s, v, d_u + 1)$ を queue に格納する。

答えは、 各危険な頂点 $v$ について、 $\mathrm{dist}_{v, 0} + \mathrm{dist}_{v, 1}$ とすればよい。

各頂点は高々 $2$ 回探索されるため計算量は $O(N + M)$ となり、本問の制約下では十分に高速である。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.constexpr int INF = 1e+9;
7. 
8.template <class T>
9.using Graph = vector<vector<T>>;
10. 
11.// ======================================== //
12. 
13.struct State
14.{
15.    int start;
16.    int now;
17.    int distance;
18.};
19. 
20.int main()
21.{
22.    int N, M;
23.    cin >> N >> M;
24.    Graph<int> G(N);
25.    rep(i, 0, M)
26.    {
27.        int U, V;
28.        cin >> U >> V;
29.        U--;
30.        V--;
31.        G[U].push_back(V);
32.        G[V].push_back(U);
33.    }
34.    string S;
35.    cin >> S;
36. 
37.    vector<vector<int>> from(N, vector<int>(2, -1));
38.    vector<vector<int>> dist(N, vector<int>(2, INF));
39. 
40.    queue<State> que;
41.    rep(i, 0, N)
42.    {
43.        if (S[i] == 'S')
44.        {
45.            from[i][0] = i;
46.            dist[i][0] = 0;
47.            que.push({i, i, 0});
48.        }
49.    }
50. 
51.    while (!que.empty())
52.    {
53.        State state = que.front();
54.        que.pop();
55. 
56.        for (int next : G[state.now])
57.        {
58.            if (from[next][0] == -1)
59.            {
60.                from[next][0] = state.start;
61.                dist[next][0] = state.distance + 1;
62.                que.push({state.start, next, state.distance + 1});
63.            }
64.            else if (from[next][0] != state.start && from[next][1] == -1)
65.            {
66.                from[next][1] = state.start;
67.                dist[next][1] = state.distance + 1;
68.                que.push({state.start, next, state.distance + 1});
69.            }
70.        }
71.    }
72. 
73.    rep(i, 0, N)
74.    {
75.        if (S[i] == 'D')
76.            cout << dist[i][0] + dist[i][1] << endl;
77.    }
78. 
79.    return 0;
80.}

https://atcoder.jp/contests/abc429/submissions/70582729

atcoder.jp

実装時間: 50 分

コメント

2 番目までの最短距離を保持する BFS は始めて実装した。 意外とシンプルに書けてびっくり。