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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc237/editorial/3346
// 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 = 202020202020202020;

struct edge{
    int n; // 次の頂点.
    LL c;  // コスト.
    bool operator < (const edge &E) const{ return c > E.c; }
};

vector<edge> G[202020];
LL h[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &h[i]);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;
        
        // 辺のコストは, 広場間の標高差の絶対値(解説通り).
        G[u].pb(edge{v, abs(h[v] - h[u])});
        G[v].pb(edge{u, abs(h[v] - h[u])});
    }
    
    // 2. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* memo){
        // 2-1. 初期化.
        priority_queue<edge> pq;
        
        // 2-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 2-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 2-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 2-5. 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
            }
        }
    };
    
    // 3. 各広場までの, 最小コスト.
    LL d[N];
    int memo[N];
    rep(i, N) d[i] = INF, memo[i] = 0;
    dijkstra(0, d, memo);
    
    // 4. 楽しさの最大値は？
    // -> 数式計算で取得した値と比較(解説通り).
    //    解説上 の d[i], H[i] - H[1] は, 偶奇が一致するので, 展開した式は, 2 で 割り切れるはず.
    LL ans = 0;
    rep(i, N) ans = max(ans, (- d[i] - 3 * h[i] + 3 * h[0])/ 2);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc237/editorial/3346

// 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 = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

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

};

vector<edge> G[202020];

LL h[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

rep(i, M){

int u, v;

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

u--;

v--;

// 辺のコストは, 広場間の標高差の絶対値(解説通り).

G[u].pb(edge{v, abs(h[v] - h[u])});

G[v].pb(edge{u, abs(h[v] - h[u])});

}

// 2. ダイクストラ法.

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

auto dijkstra = [&](int s, LL* d, int* memo){

// 2-1. 初期化.

priority_queue<edge> pq;

// 2-2. 始点設定.

d[s] = 0;

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

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

while(!pq.empty()){

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

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

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

if(memo[cn]) continue;

memo[cn]++;

// 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.

for(auto &g : G[cn]){

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

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

}

};

// 3. 各広場までの, 最小コスト.

LL d[N];

int memo[N];

rep(i, N) d[i] = INF, memo[i] = 0;

dijkstra(0, d, memo);

// 4. 楽しさの最大値は？

// -> 数式計算で取得した値と比較(解説通り).

// 解説上の d[i], H[i] - H[1] は, 偶奇が一致するので, 展開した式は, 2 で割り切れるはず.

LL ans = 0;

rep(i, N) ans = max(ans, (- d[i] - 3 * h[i] + 3 * h[0])/ 2);

// 5. 出力.

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

return 0;

}

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

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

[入力例]
2 1
0 10
1 2

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

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

[出力例]
5

[入力例]
10 16
314 159 265 358 979 323 846 264 338 327
1 2
1 3
2 4
2 5
3 5
3 6
4 8
4 9
5 7
5 8
6 7
6 10
7 8
7 10
8 9
9 10

[出力例]
155

[入力例]

4 4

10 8 12 5

1 2

1 3

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

2 1

0 10

1 2

[出力例]

※AtCoderテストケースより

[入力例]

5 7

12 7 13 10 8

1 2

1 4

1 5

2 3

2 4

2 5

3 5

[出力例]

[入力例]

10 16

314 159 265 358 979 323 846 264 338 327

1 2

1 3

2 4

2 5

3 5

3 6

4 8

4 9

5 7

5 8

6 7

6 10

7 8

7 10

8 9

9 10

[出力例]

155

■参照サイト
AtCoder Beginner Contest 237

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

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

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

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