回答編集履歴
1
具体例追記
answer
CHANGED
|
@@ -5,4 +5,42 @@
|
|
|
5
5
|
|
|
6
6
|
`prev_v[cur]`は、`cur`の前の頂点のインデックスになります。
|
|
7
7
|
そして、`G[cur]`は、`cur`につながる辺の`vector`になります。
|
|
8
|
-
辺の`vector`について、頂点のインデックス番目の要素を取得しているのが誤りです。
|
|
8
|
+
辺の`vector`について、頂点のインデックス番目の要素を取得しているのが誤りです。
|
|
9
|
+
|
|
10
|
+
---
|
|
11
|
+
具体的に、サンプル1で何が起こっているかを順に追っていきましょう。
|
|
12
|
+
|
|
13
|
+
まず、入力の読み込みで、A,Gはそれぞれ以下のようになります。
|
|
14
|
+
({}はvector、()はpairのつもりです)
|
|
15
|
+
|
|
16
|
+
A = { 1, 2, 1, 0, 3 };
|
|
17
|
+
G = { { (1,0) }, { (0,0), (2,1) }, { (1,1), (3,2) }, { (2,2) } };
|
|
18
|
+
|
|
19
|
+
読み込んだ後のforループで、i = 1 の場合の処理を追ってみましょう。
|
|
20
|
+
|
|
21
|
+
まず、
|
|
22
|
+
```c++
|
|
23
|
+
prev_v.assign(N, INF);
|
|
24
|
+
prev_v[A[i]] = -1;
|
|
25
|
+
dfs(A[i], A[i + 1]);
|
|
26
|
+
```
|
|
27
|
+
|
|
28
|
+
により、prev_vは以下のようになります。
|
|
29
|
+
|
|
30
|
+
prev_v = { INF, 2, -1, 2 };
|
|
31
|
+
|
|
32
|
+
次に、
|
|
33
|
+
```c++
|
|
34
|
+
int cur = A[i + 1];
|
|
35
|
+
```
|
|
36
|
+
|
|
37
|
+
により、cur = 1 となります。
|
|
38
|
+
|
|
39
|
+
その次の`while`の条件は当然満たすとして、問題の以下の処理について考えます。
|
|
40
|
+
```c++
|
|
41
|
+
int edge_id = G[cur][prev_v[cur]].second;
|
|
42
|
+
```
|
|
43
|
+
|
|
44
|
+
G[cur] = { (0,0), (2,1) }、prev_v[cur] = 2 なので、
|
|
45
|
+
G[cur][prev_v[cur]] は、{ (0,0), (2,1) } の2番目の要素を取得しようとします。
|
|
46
|
+
しかし、要素が2つしかないので範囲外アクセスとなります。
|