C++ の動作確認をしてみた（８５０）

C++の練習を兼ねて, AtCoder Beginner Contest 277 の問題E (Crystal Switches) を解いてみた.

■感想.
1. 問題E は, 方針を絞り込んだものの WA版となったため, 解説を確認(※)し, 再提出したところ, AC版に到達できた.
※頂点(N) と仮想的な頂点(2 * N) の両方を確認してから, 出力する考慮が漏れていた.
2. 個人的には, 01-BFS を復習出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc277/editorial/5204
// 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 pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
const int INF = 2020202020;

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vvi G(2 * N);
    rep(i, M){
        int u, v, a;
        scanf("%d %d %d", &u, &v, &a);
        --u, --v;
        
        // 初回, 通行不可能な辺は, 仮想的な頂点(頂点番号が, N 大きい)から作成.
        u += !a * N;
        v += !a * N;
        G[u].pub(v);
        G[v].pub(u);
    }
    rep(i, K){
        // スイッチは, 頂点と仮想的な頂点を結ぶ辺とみなす.
        int s;
        scanf("%d", &s);
        --s;
        G[s + 0].pub(s + N);
        G[s + N].pub(s + 0);
    }
    
    // 2. 01-BFS.
    // https://ja.wikipedia.org/wiki/幅優先探索
    // https://betrue12.hateblo.jp/entry/2018/12/08/000020
    auto bfs01 = [&](int s, int* d){
        // 2-1. 空のキュー.
        deque<int> dq;
        
        // 2-2. 探索開始地点 s の コスト設定.
        d[s] = 0;
        
        // 2-3. 探索開始地点 s をキュー に追加.
        dq.pub(s);
        while(!dq.empty()){
            // 2-4. キュー の 先頭要素を取り出す.
            int u = dq.front();
            dq.pof();
            
            // 2-5. 隣接頂点を確認.
            for(auto &v : G[u]){
                // コスト 0.
                if(abs(u - v) == N && d[v] > d[u] + 0) d[v] = d[u] + 0, dq.puf(v);
                
                // コスト 1.
                if(abs(u - v) != N && d[v] > d[u] + 1) d[v] = d[u] + 1, dq.pub(v);
            }
        }
    };
    int d[2 * N];
    rep(i, 2 * N) d[i] = INF;
    bfs01(0, d);
    
    // 3. 出力.
    int ans = min(d[N - 1], d[2 * N - 1]);
    printf("%d\n", (ans == INF) ? -1 : ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc277/editorial/5204

// 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 pof pop_front

#define pob pop_back

#define pub push_back

#define puf push_front

const int INF = 2020202020;

int main(){

// 1. 入力情報.

int N, M, K;

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

vvi G(2 * N);

rep(i, M){

int u, v, a;

scanf("%d %d %d", &u, &v, &a);

--u, --v;

// 初回, 通行不可能な辺は, 仮想的な頂点(頂点番号が, N 大きい)から作成.

u += !a * N;

v += !a * N;

G[u].pub(v);

G[v].pub(u);

}

rep(i, K){

// スイッチは, 頂点と仮想的な頂点を結ぶ辺とみなす.

int s;

scanf("%d", &s);

--s;

G[s + 0].pub(s + N);

G[s + N].pub(s + 0);

}

// 2. 01-BFS.

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

// https://betrue12.hateblo.jp/entry/2018/12/08/000020

auto bfs01 = [&](int s, int* d){

// 2-1. 空のキュー.

deque<int> dq;

// 2-2. 探索開始地点 s のコスト設定.

d[s] = 0;

// 2-3. 探索開始地点 s をキューに追加.

dq.pub(s);

while(!dq.empty()){

// 2-4. キューの先頭要素を取り出す.

int u = dq.front();

dq.pof();

// 2-5. 隣接頂点を確認.

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

// コスト 0.

if(abs(u - v) == N && d[v] > d[u] + 0) d[v] = d[u] + 0, dq.puf(v);

// コスト 1.

if(abs(u - v) != N && d[v] > d[u] + 1) d[v] = d[u] + 1, dq.pub(v);

}

};

int d[2 * N];

rep(i, 2 * N) d[i] = INF;

bfs01(0, d);

// 3. 出力.

int ans = min(d[N - 1], d[2 * N - 1]);

printf("%d\n", (ans == INF) ? -1 : ans);

return 0;

}

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

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

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

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

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

[出力例]
5

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

[出力例]
7

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

[出力例]
10

[入力例]

5 5 2

1 3 0

2 3 1

5 4 1

2 1 1

1 4 0

3 4

[出力例]

※AtCoderのテストケースより

[入力例]

4 4 2

4 3 0

1 2 1

1 2 0

2 1 1

2 4

[出力例]

-1

※AtCoderのテストケースより

[入力例]

7 8 6

1 2 1

3 4 1

5 6 1

7 6 1

4 2 0

3 5 0

5 7 0

6 7 0

2 3 4 5 6 7

[出力例]

[入力例]

10 10 8

1 2 1

3 2 0

3 4 1

5 6 1

5 3 0

6 7 0

7 8 1

7 9 0

8 10 0

9 10 1

2 3 5 6 7 8 9 10

[出力例]

[入力例]

18 23 15

1 2 1

1 3 1

3 2 0

3 5 0

4 5 1

4 6 1

6 5 0

5 8 1

8 7 1

8 9 1

7 9 0

11 9 0

11 10 1

11 12 1

12 10 0

12 14 1

14 13 0

13 15 1

14 15 0

15 16 1

16 17 0

17 18 0

16 18 1

2 3 5 6 7 9 10 11 12 13 14 15 16 17 18

[出力例]

■参照サイト
大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)
01-BFSのちょっと丁寧な解説

C++の練習を兼ねて, AtCoder Beginner Contest 277 の 問題E (Crystal Switches) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 277 の問題E (Crystal Switches) を解いてみた.

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