回答編集履歴
5
G[pos][i] の値を全部追加
test
CHANGED
|
@@ -29,12 +29,12 @@
|
|
|
29
29
|
G の要素数は 100009 ですが、使っているのは G[1]～G[6] の 6個だけです。
|
|
30
30
|
G は vector<int> を要素とする配列です。
|
|
31
31
|
```
|
|
32
|
-
G[1] = {2, 3} G[1].size() = 2
|
|
32
|
+
G[1] = {2, 3} G[1].size() = 2 G[1][0] = 2, G[1][1] = 3
|
|
33
|
-
G[2] = {1,
|
|
33
|
+
G[2] = {1, 5, 4} G[2].size() = 3 G[2][0] = 1, G[2][1] = 5, G[2][2] = 4
|
|
34
|
-
G[3] = {1, 4} G[3].size() = 2
|
|
34
|
+
G[3] = {1, 4} G[3].size() = 2 G[3][0] = 1, G[3][1] = 4
|
|
35
|
+
G[4] = {3, 2, 6} G[4].size() = 3 G[4][0] = 3, G[4][1] = 2, G[4][2] = 6
|
|
35
|
-
G[
|
|
36
|
+
G[5] = {2, 6} G[5].size() = 2 G[5][0] = 2, G[5][1] = 6
|
|
36
|
-
G[5] = {3, 2, 6} G[5].size() = 3
|
|
37
|
-
G[6] = {4, 5} G[6].size() = 2
|
|
37
|
+
G[6] = {4, 5} G[6].size() = 2 G[6][0] = 4, G[6][1] = 5
|
|
38
38
|
```
|
|
39
39
|
for文は G[pos].size() の合計の 14回まわっています。
|
|
40
40
|
|
4
実行結果の追加
test
CHANGED
|
@@ -84,4 +84,18 @@
|
|
|
84
84
|
6 7
|
|
85
85
|
1 2 1 3 2 5 3 4 4 2 4 6 5 6
|
|
86
86
|
```
|
|
87
|
-
|
|
87
|
+
実行結果
|
|
88
|
+
```
|
|
89
|
+
G[1]: 2 3
|
|
90
|
+
G[2]: 1 5 4
|
|
91
|
+
G[3]: 1 4
|
|
92
|
+
G[5]: 2 6
|
|
93
|
+
G[4]: 3 2 6
|
|
94
|
+
G[6]: 4 5
|
|
95
|
+
0
|
|
96
|
+
1
|
|
97
|
+
1
|
|
98
|
+
2
|
|
99
|
+
2
|
|
100
|
+
3
|
|
101
|
+
```
|
3
追記2
test
CHANGED
|
@@ -14,3 +14,74 @@
|
|
|
14
14
|
}
|
|
15
15
|
cout << endl; // ★
|
|
16
16
|
```
|
|
17
|
+
**追記2**
|
|
18
|
+
|
|
19
|
+
> 2: ...＊１４と続いているのですが
|
|
20
|
+
|
|
21
|
+
2:/3:/ ... 4:/5:/ (ただし / は改行) と続いています。
|
|
22
|
+
|
|
23
|
+
> [pos][i]と二つの配列があるのに
|
|
24
|
+
|
|
25
|
+
2つの添字がありますが、配列は 1つの G だけです。
|
|
26
|
+
|
|
27
|
+
> .size()はG[]配列では[123456]と６要素しかないはずなのに１４回for文が回っています。
|
|
28
|
+
|
|
29
|
+
G の要素数は 100009 ですが、使っているのは G[1]～G[6] の 6個だけです。
|
|
30
|
+
G は vector<int> を要素とする配列です。
|
|
31
|
+
```
|
|
32
|
+
G[1] = {2, 3} G[1].size() = 2
|
|
33
|
+
G[2] = {1, 4, 5} G[2].size() = 3
|
|
34
|
+
G[3] = {1, 4} G[3].size() = 2
|
|
35
|
+
G[4] = {2, 6} G[4].size() = 2
|
|
36
|
+
G[5] = {3, 2, 6} G[5].size() = 3
|
|
37
|
+
G[6] = {4, 5} G[6].size() = 2
|
|
38
|
+
```
|
|
39
|
+
for文は G[pos].size() の合計の 14回まわっています。
|
|
40
|
+
|
|
41
|
+
ところで、100009 という数字はどこから来ているのですか？
|
|
42
|
+
C++ では vector が使えるのですから、必要な個数だけ用意すればいいでしょう。
|
|
43
|
+
```C++
|
|
44
|
+
#include <iostream>
|
|
45
|
+
#include <vector>
|
|
46
|
+
#include <queue>
|
|
47
|
+
using namespace std;
|
|
48
|
+
|
|
49
|
+
int main()
|
|
50
|
+
{
|
|
51
|
+
int N, M, A, B;
|
|
52
|
+
cin >> N >> M;
|
|
53
|
+
vector<int> dist(N+1, -1); // 初期値: -1(未到達)
|
|
54
|
+
vector<vector<int>> G(N+1);
|
|
55
|
+
for (int i = 0; i < M; i++) {
|
|
56
|
+
cin >> A >> B;
|
|
57
|
+
G[A].push_back(B);
|
|
58
|
+
G[B].push_back(A);
|
|
59
|
+
}
|
|
60
|
+
queue<int> Q; // 距離が求まった頂点
|
|
61
|
+
dist[1] = 0; // 頂点1 は距離 0
|
|
62
|
+
Q.push(1); // 頂点1 は距離確定
|
|
63
|
+
|
|
64
|
+
while (!Q.empty()) {
|
|
65
|
+
int pos = Q.front(); // Q の先頭を調べる（操作 2）
|
|
66
|
+
Q.pop();
|
|
67
|
+
cout << "G[" << pos << "]:";
|
|
68
|
+
for (int i = 0; i < (int)G[pos].size(); i++) {
|
|
69
|
+
int nex = G[pos][i];
|
|
70
|
+
cout << " " << nex;
|
|
71
|
+
if (dist[nex] == -1) {
|
|
72
|
+
dist[nex] = dist[pos] + 1;
|
|
73
|
+
Q.push(nex); // Q に nex を追加（操作 1）
|
|
74
|
+
}
|
|
75
|
+
}
|
|
76
|
+
cout << endl;
|
|
77
|
+
}
|
|
78
|
+
// 頂点 1 から各頂点までの最短距離を出力
|
|
79
|
+
for (int i = 1; i <= N; i++) cout << dist[i] << endl;
|
|
80
|
+
}
|
|
81
|
+
```
|
|
82
|
+
入力
|
|
83
|
+
```
|
|
84
|
+
6 7
|
|
85
|
+
1 2 1 3 2 5 3 4 4 2 4 6 5 6
|
|
86
|
+
```
|
|
87
|
+
|
2
コードの修正
test
CHANGED
|
@@ -6,7 +6,7 @@
|
|
|
6
6
|
cout << pos << ":"; // ★
|
|
7
7
|
for (int i = 0; i < (int)G[pos].size(); i++) {
|
|
8
8
|
int nex = G[pos][i];
|
|
9
|
-
cout << " " <<
|
|
9
|
+
cout << " " << nex; // ★
|
|
10
10
|
if (dist[nex] == -1) {
|
|
11
11
|
dist[nex] = dist[pos] + 1;
|
|
12
12
|
Q.push(nex); // Q に nex を追加（操作 1）
|
1
追記
test
CHANGED
|
@@ -1 +1,16 @@
|
|
|
1
1
|
6 7 の入力の後、辺の読み込みを 7組しかしていません。入力データは 14 行ありますよ。
|
|
2
|
+
|
|
3
|
+
**追記**
|
|
4
|
+
G[pos][i] の値を表示したければ、次のようにすればよいでしょう。
|
|
5
|
+
```C++
|
|
6
|
+
cout << pos << ":"; // ★
|
|
7
|
+
for (int i = 0; i < (int)G[pos].size(); i++) {
|
|
8
|
+
int nex = G[pos][i];
|
|
9
|
+
cout << " " << G[pos][i]; // ★
|
|
10
|
+
if (dist[nex] == -1) {
|
|
11
|
+
dist[nex] = dist[pos] + 1;
|
|
12
|
+
Q.push(nex); // Q に nex を追加（操作 1）
|
|
13
|
+
}
|
|
14
|
+
}
|
|
15
|
+
cout << endl; // ★
|
|
16
|
+
```
|