C++ の動作確認をしてみた（４０７）

C++の練習を兼ねて, AtCoder Beginner Contest 035 の問題D (トレジャーハント)を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Beginner Contest 035 解説をご覧下さい.

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

// 解き直し.
// https://www.slideshare.net/chokudai/abc035
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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
const LL INF = 101010101010101010;

struct edge{
    int n; // 次の頂点.
    LL c;  // 移動時間.
    bool operator < (const edge &E) const{ return c > E.c; }
};

LL a[101010];  // 所持金.
LL d1[101010]; // 1 -> i の 最短移動時間.
LL di[101010]; // i -> 1 の 最短移動時間.
vector<edge> G[2][101010]; // 第一成分: 往路／復路, 第二成分: 各グラフ情報.

// https://ja.wikipedia.org/wiki/ダイクストラ法
// @param s: 今回探索する頂点番号.
// @param d: 最短距離を保存.
// @param f: 往路／復路の区分.
// @return: 特に無し.
void dijkstra(int s, LL* d, int f){
    // 1. 初期化.
    priority_queue<edge> pq;
    
    // 2. 始点設定.
    d[s] = 0;
    pq.push({s, 0LL});
    
    // 3. キュー pq が 空になるまで, 探索.
    while(!pq.empty()){
        // 4. 探索を継続するために, 頂点を取得.
        edge e = pq.top();
        pq.pop();
        int cn = e.n;
        LL cc = e.c;
        
        // 5. 各隣接する頂点について, 移動時間の確認／更新.
        rep(i, G[f][cn].size()){
            edge ne = G[f][cn][i];
            int nn = ne.n;
            LL nc = cc + ne.c;
            
            // 6. 移動時間更新.
            if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    LL T, ans = 0;
    scanf("%d %d %lld", &N, &M, &T);
    rep(i, N) scanf("%lld", &a[i]);
    rep(i, M){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        a--, b--;
        
        // 往路.
        edge ef;
        ef.n = b;
        ef.c = c;
        G[0][a].pb(ef);
        
        // 復路.
        edge eb;
        eb.n = a;
        eb.c = c;
        G[1][b].pb(eb);
    }
    rep(i, 101010) d1[i] = di[i] = INF;
    
    // 2. 頂点 1 から 各頂点までの, 最短経路(往路／復路)を求める.
    dijkstra(0, d1, 0);
    dijkstra(0, di, 1);
    
    // 3. 所持金の最大値は？
    rep(i, N){
        LL m = a[i] * max(0LL, T - d1[i] - di[i]);
        ans = max(ans, m);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://www.slideshare.net/chokudai/abc035

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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

const LL INF = 101010101010101010;

struct edge{

int n; // 次の頂点.

LL c; // 移動時間.

bool operator < (const edge &E) const{ return c > E.c; }

};

LL a[101010]; // 所持金.

LL d1[101010]; // 1 -> i の最短移動時間.

LL di[101010]; // i -> 1 の最短移動時間.

vector<edge> G[2][101010]; // 第一成分: 往路／復路, 第二成分: 各グラフ情報.

// https://ja.wikipedia.org/wiki/ダイクストラ法

// @param s: 今回探索する頂点番号.

// @param d: 最短距離を保存.

// @param f: 往路／復路の区分.

// @return: 特に無し.

void dijkstra(int s, LL* d, int f){

// 1. 初期化.

priority_queue<edge> pq;

// 2. 始点設定.

d[s] = 0;

pq.push({s, 0LL});

// 3. キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 4. 探索を継続するために, 頂点を取得.

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 5. 各隣接する頂点について, 移動時間の確認／更新.

rep(i, G[f][cn].size()){

edge ne = G[f][cn][i];

int nn = ne.n;

LL nc = cc + ne.c;

// 6. 移動時間更新.

if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});

}

return;

}

int main(){

// 1. 入力情報.

int N, M;

LL T, ans = 0;

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

rep(i, N) scanf("%lld", &a[i]);

rep(i, M){

int a, b;

LL c;

scanf("%d %d %lld", &a, &b, &c);

a--, b--;

// 往路.

edge ef;

ef.n = b;

ef.c = c;

G[0][a].pb(ef);

// 復路.

edge eb;

eb.n = a;

eb.c = c;

G[1][b].pb(eb);

}

rep(i, 101010) d1[i] = di[i] = INF;

// 2. 頂点 1 から各頂点までの, 最短経路(往路／復路)を求める.

dijkstra(0, d1, 0);

dijkstra(0, di, 1);

// 3. 所持金の最大値は？

rep(i, N){

LL m = a[i] * max(0LL, T - d1[i] - di[i]);

ans = max(ans, m);

}

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]
11 20 345
7 1 7 1 4 7 5 2 7 2 11
6 4 7
8 3 19
2 8 15
6 8 2
7 10 9
8 11 8
4 9 17
6 7 10
9 10 3
8 5 18
9 8 25
11 7 24
3 7 17
11 6 2
2 7 16
7 5 24
5 9 2
4 10 24
4 1 1
7 3 3

[出力例]
2415

[入力例]
23 32 2021
3 15 14 17 1 4 21 19 41 52 83 77 9 16 70 10 27 55 66 22 15 13 61
1 10 38
16 14 37
5 1 55
19 7 42
20 23 36
13 1 50
5 22 31
21 9 58
10 12 58
19 2 29
20 13 65
2 19 73
17 2 61
22 5 24
15 16 29
10 9 72
12 15 61
4 21 36
15 12 56
16 6 37
12 7 71
1 5 40
7 1 25
10 2 50
20 15 34
1 3 39
17 20 23
10 7 38
17 14 35
7 9 60
3 5 59
21 8 53

[出力例]
140833

100

101

102

103

104

105

106

107

108

[入力例]

2 2 5

1 3

1 2 2

2 1 1

[出力例]

※AtCoderテストケースより

[入力例]

2 2 3

1 3

1 2 2

2 1 1

[出力例]

※AtCoderテストケースより

[入力例]

8 15 120

1 2 6 16 1 3 11 9

1 8 1

7 3 14

8 2 13

3 5 4

5 7 5

6 4 1

6 8 17

7 8 5

1 4 2

4 7 1

6 1 3

3 1 10

2 6 5

2 4 12

5 1 30

[出力例]

1488

※AtCoderテストケースより

[入力例]

11 20 345

7 1 7 1 4 7 5 2 7 2 11

6 4 7

8 3 19

2 8 15

6 8 2

7 10 9

8 11 8

4 9 17

6 7 10

9 10 3

8 5 18

9 8 25

11 7 24

3 7 17

11 6 2

2 7 16

7 5 24

5 9 2

4 10 24

4 1 1

7 3 3

[出力例]

2415

[入力例]

23 32 2021

3 15 14 17 1 4 21 19 41 52 83 77 9 16 70 10 27 55 66 22 15 13 61

1 10 38

16 14 37

5 1 55

19 7 42

20 23 36

13 1 50

5 22 31

21 9 58

10 12 58

19 2 29

20 13 65

2 19 73

17 2 61

22 5 24

15 16 29

10 9 72

12 15 61

4 21 36

15 12 56

16 6 37

12 7 71

1 5 40

7 1 25

10 2 50

20 15 34

1 3 39

17 20 23

10 7 38

17 14 35

7 9 60

3 5 59

21 8 53

[出力例]

140833

■参照サイト
AtCoder Beginner Contest 035

C++の練習を兼ねて, AtCoder Beginner Contest 035 の 問題D (トレジャーハント)を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 035 の問題D (トレジャーハント)を解いてみた.

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