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

C++の練習を兼ねて, AtCoder Beginner Contest 302 の問題F (Merge Set) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 302 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc302/editorial/6411
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N + M);
    rep(i, N){
        int a;
        scanf("%d", &a);
        rep(j, a){
            int s;
            scanf("%d", &s);
            --s;
            G[i + 0].pb(s + N);
            G[s + N].pb(i + 0);
        }
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    int d[N + M];
    rep(i, N + M) d[i] = 0;
    bfs(G, N, d);
    
    // 3. 出力.
    printf("%d\n", d[N + M - 1] ? d[N + M - 1] / 2 - 1 : -1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc302/editorial/6411

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

vvi G(N + M);

rep(i, N){

int a;

scanf("%d", &a);

rep(j, a){

int s;

scanf("%d", &s);

--s;

G[i + 0].pb(s + N);

G[s + N].pb(i + 0);

}

// 2. bfs.

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

auto bfs = [&](vvi &G, int s, int* d){

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 隣接頂点をチェック.

for(auto &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);

}

};

int d[N + M];

rep(i, N + M) d[i] = 0;

bfs(G, N, d);

// 3. 出力.

printf("%d\n", d[N + M - 1] ? d[N + M - 1] / 2 - 1 : -1);

return 0;

}

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

[出力例]
2
※AtCoderテストケースより

[入力例]
1 2
2
1 2

[出力例]
0
※AtCoderテストケースより

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

[出力例]
-1
※AtCoderテストケースより

[入力例]
4 8
3
1 3 5
2
1 2
3
2 4 7
4
4 6 7 8

[出力例]
2
※AtCoderテストケースより

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

[出力例]
3

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

[出力例]
5

[入力例]

3 5

1 2

2 3

3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

1 2

[出力例]

※AtCoderテストケースより

[入力例]

3 5

1 3

2 4

2 4 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 8

1 3 5

1 2

2 4 7

4 6 7 8

[出力例]

※AtCoderテストケースより

[入力例]

5 10

1 2

1 3 4

3 5 6

6 8

8 9 10

[出力例]

[入力例]

8 15

1 2

2 3 4

5 6

8 9 7

5 9 10 4

10 11

12 13 11

12 14 15

[出力例]

■参照サイト
トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)

C++の練習を兼ねて, AtCoder Beginner Contest 302 の 問題F (Merge Set) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 302 の問題F (Merge Set) を解いてみた.

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