C++ の動作確認をしてみた（９３）

C++の練習を兼ねて, AtCoder Beginner Contest 126 の問題D (D – Even Relation) を解いてみた.

■感想.
1. グラフの幅優先探索について, 復習できたので良かったと思う.
2. とりあえず, 解説見ずに解けたので良かったと思う.
3. bfs関数の第一引数を, G から &G に変更したところ, 実行時間が, 76[ms] から 59[ms] に改善した.

本家のサイトABC 126解説をご覧下さい.

■C++版プログラム(問題D／AC版).

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int MAX = 1e5 + 1;
struct edge{
    int v; // 次の頂点.
    LL  w; // 距離.
};
LL dist[MAX]; // 距離を保存

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @return: 特に無し.
void bfs(vector<vector<edge>> &G, int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    dist[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){

        // 4. キューから取り出す.
        int u = q.front();
        q.pop();

        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            // cout << "u=" << u << " e.v=" << e.v << " e.w=" << e.w << endl;
            if(dist[e.v] > 0)              continue;
            if(dist[e.v] == 0 && e.v != s) dist[e.v] = dist[u] + e.w, q.push(e.v);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    vector<vector<edge>> graph(N);
    for(LL i = 0; i < N - 1; i++){
        int u, v;
        LL w;
        scanf("%d %d %lld", &u, &v, &w);
        edge e1, e2;
        u--, v--;
        // u -> v
        e1.v = v, e1.w = w;
        graph[u].push_back(e1);
        // v -> u
        e2.v = u, e2.w = w;
        graph[v].push_back(e2);
    }
    
    // 2. 頂点を一つ固定して, そこから各頂点への距離を保存.
    bfs(graph, 0);
    // for(int i = 0; i < N; i++) printf("%lld ", dist[i]);
    // printf("\n");
    
    // 3. 出力 ～ 後処理.
    // 頂点 0 からの距離が, 偶数: 白色, 奇数: 黒色.
    for(int i = 0; i < N; i++){
        LL d = dist[i];
        if(d % 2 == 0) printf("%d\n", 0);
        else           printf("%d\n", 1);
    }
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

constexpr int MAX = 1e5 + 1;

struct edge{

int v; // 次の頂点.

LL w; // 距離.

};

LL dist[MAX]; // 距離を保存

// グラフを幅優先探索する.

// https://ja.wikipedia.org/wiki/幅優先探索

// ※bfsの動作確認用.

// @param G: グラフ.

// @param s: グラフの探索開始頂点.

// @return: 特に無し.

void bfs(vector<vector<edge>> &G, int s){

// 1. 空のキュー.

queue<int> q;

// 2. 訪問済みフラグ設定.

// ※スタート地点は, 距離ゼロを指定.

dist[s] = 0;

// 3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 4. キューから取り出す.

int u = q.front();

q.pop();

// 5. 取り出した要素を処理.

for(auto &e : G[u]){

// 6. 訪問済であれば, 処理をスキップ.

// cout << "u=" << u << " e.v=" << e.v << " e.w=" << e.w << endl;

if(dist[e.v] > 0) continue;

if(dist[e.v] == 0 && e.v != s) dist[e.v] = dist[u] + e.w, q.push(e.v);

}

return;

}

int main() {

// 1. 入力情報取得.

int N;

scanf("%d", &N);

vector<vector<edge>> graph(N);

for(LL i = 0; i < N - 1; i++){

int u, v;

LL w;

scanf("%d %d %lld", &u, &v, &w);

edge e1, e2;

u--, v--;

// u -> v

e1.v = v, e1.w = w;

graph[u].push_back(e1);

// v -> u

e2.v = u, e2.w = w;

graph[v].push_back(e2);

}

// 2. 頂点を一つ固定して, そこから各頂点への距離を保存.

bfs(graph, 0);

// for(int i = 0; i < N; i++) printf("%lld ", dist[i]);

// printf("\n");

// 3. 出力～後処理.

// 頂点 0 からの距離が, 偶数: 白色, 奇数: 黒色.

for(int i = 0; i < N; i++){

LL d = dist[i];

if(d % 2 == 0) printf("%d\n", 0);

else printf("%d\n", 1);

}

return 0;

}

[入力例]
3
1 2 2
2 3 1

[出力例(debug版)]
0 2 3 
0
0
1
※AtCoderテストケースより

[入力例]
5
2 5 2
2 3 10
1 3 8
3 4 2

[出力例(debug版)]
0 18 8 10 20 
0
0
0
0
0
※AtCoderテストケースより

[入力例]
5
1 2 2
1 3 1
1 4 1
1 5 1

[出力例(debug版)]
0 2 1 1 1 
0
0
1
1
1

[入力例]
15
1 2 2
2 3 3
3 4 4
4 13 5
3 14 6
2 5 7
5 8 8
8 9 9
5 6 10
6 10 11
10 11 12
11 12 13
6 7 14
7 15 15

[出力例(debug版)]
0 2 5 9 9 19 33 17 26 30 42 55 14 11 48 
0
0
1
1
1
1
1
1
0
0
0
1
0
1
0

[入力例]

1 2 2

2 3 1

[出力例(debug版)]

0 2 3

※AtCoderテストケースより

[入力例]

2 5 2

2 3 10

1 3 8

3 4 2

[出力例(debug版)]

0 18 8 10 20

※AtCoderテストケースより

[入力例]

1 2 2

1 3 1

1 4 1

1 5 1

[出力例(debug版)]

0 2 1 1 1

[入力例]

1 2 2

2 3 3

3 4 4

4 13 5

3 14 6

2 5 7

5 8 8

8 9 9

5 6 10

6 10 11

10 11 12

11 12 13

6 7 14

7 15 15

[出力例(debug版)]

0 2 5 9 9 19 33 17 26 30 42 55 14 11 48

■参照サイト
AtCoder Beginner Contest 126

C++の練習を兼ねて, AtCoder Beginner Contest 126 の 問題D (D – Even Relation) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 126 の問題D (D – Even Relation) を解いてみた.

コメントを残すコメントをキャンセル