C++ の動作確認をしてみた（６１６）

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題K (ガソリンスタンド) を解いてみた.

■感想.
1. 問題Kは, 方針を絞り込めたので, AC版に到達できた.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

// 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
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N, M, Q, K;
    scanf("%d %d %d %d", &N, &M, &Q, &K);
    vi gasStation;
    map<int, int> m;
    rep(i, K){
        int a;
        scanf("%d", &a);
        a--;
        gasStation.pb(a);
        m[a] = 1;
    }
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. ガソリンスタンドの番号付け.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, vvi &d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!d[m[s]][e] && e != s) d[m[s]][e] = d[m[s]][u] + 1, q.push(e);
        }
    };
    
    // 4. 各ガソリンスタンドから, 各街までの最短距離.
    vvi d(K, vi(N));
    for(auto &p : gasStation) bfs(G, p, d);
    
    // 5. クエリ回答.
    rep(i, Q){
        // クエリ情報.
        int s, t;
        scanf("%d %d", &s, &t);
        s--, t--;
        
        // 道を通る回数の最小値.
        int ans = 2020202020;
        for(auto &p : gasStation) ans = min(ans, d[m[p]][s] + d[m[p]][t]);
        
        // 出力.
        printf("%d\n", ans);
    }
    return 0;
    
}

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int N, M, Q, K;

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

vi gasStation;

map<int, int> m;

rep(i, K){

int a;

scanf("%d", &a);

a--;

gasStation.pb(a);

m[a] = 1;

}

vvi G(N);

rep(i, M){

int u, v;

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

u--;

v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. ガソリンスタンドの番号付け.

int idx = -1;

for(auto &p : m) p.b = ++idx;

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

// 4. 各ガソリンスタンドから, 各街までの最短距離.

vvi d(K, vi(N));

for(auto &p : gasStation) bfs(G, p, d);

// 5. クエリ回答.

rep(i, Q){

// クエリ情報.

int s, t;

scanf("%d %d", &s, &t);

s--, t--;

// 道を通る回数の最小値.

int ans = 2020202020;

for(auto &p : gasStation) ans = min(ans, d[m[p]][s] + d[m[p]][t]);

// 出力.

printf("%d\n", ans);

}

return 0;

}

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

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

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

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

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

[出力例]
3
4
3
5
3
3
5

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

[出力例]
2
3
4
5
4
5
5
5
5
5

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

3 2 1 1

1 2

2 3

3 2

[出力例]

※AtCoderテストケースより

[入力例]

5 6 2 2

3 1

1 2

2 3

2 4

1 5

2 5

3 5

5 5

5 4

[出力例]

※AtCoderテストケースより

[入力例]

12 15 7 3

9 3 11

1 2

1 3

2 4

2 5

3 5

5 6

5 11

6 8

6 7

7 8

7 9

8 10

8 12

9 10

11 12

1 2

5 4

1 6

1 10

5 8

5 6

2 7

[出力例]

[入力例]

20 28 10 5

7 3 15 16 17

1 2

1 3

2 5

2 6

2 7

3 4

3 5

4 9

5 8

6 11

7 12

8 9

8 10

8 11

8 13

9 10

11 12

11 13

11 14

13 15

13 17

13 18

14 16

15 16

17 19

17 20

18 19

19 20

1 5

1 12

1 10

1 14

8 14

2 20

4 19

10 11

10 14

10 18

[出力例]

■参照サイト
第九回アルゴリズム実技検定

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題K (ガソリンスタンド) を解いてみた.

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題K (ガソリンスタンド) を解いてみた.

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