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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題I (直通エレベーター) を解いてみた.

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

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

// 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 a first
#define b second
#define pb push_back
const LL INF = 2e18 + 1;

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

vector<edge> G[202020];
LL a[101010], b[101010], c[101010];

int main(){
    
    // 1. 入力情報.
    LL N;
    int M;
    scanf("%lld %d", &N, &M);
    map<LL, int> m;
    rep(i, M){
        scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);
        m[a[i]] = 1;
        m[b[i]] = 1;
    }
    m[1] = 1;
    m[N] = 1;
    
    // 2. 座標圧縮.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 3. グラフ構築(階段).
    LL cBef, cCur;
    int vBef = -1, vCur;
    for(auto &p : m){
        // 今回分更新.
        cCur = p.a;
        vCur = p.b;
        
        // 辺を追加.
        if(vBef != -1){
            G[vBef].pb(edge{vCur, cCur - cBef});
            G[vCur].pb(edge{vBef, cCur - cBef});
        }
        
        // 前回分更新.
        cBef = cCur;
        vBef = vCur;
    }
    
    // 4. グラフ構築(エレベーター).
    rep(i, M){
        int u = m[a[i]];
        int v = m[b[i]];
        G[u].pb(edge{v, c[i]});
        G[v].pb(edge{u, c[i]});
    }
    
    // 5. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* memo){
        // 初期化.
        priority_queue<edge> pq;
        
        // 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            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});
            }
        }
    };
    
    // 6. 各頂点までの, 最短コストを求める.
    LL d[idx + 1];     // 頂点 0 からの距離.
    int memo[idx + 1]; // 訪問済みフラグ.
    rep(i, idx + 1) d[i] = INF, memo[i] = 0;
    dijkstra(0, d, memo);
    
    // 7. 出力.
    printf("%lld\n", d[idx]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

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

#define b second

#define pb push_back

const LL INF = 2e18 + 1;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

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

};

vector<edge> G[202020];

LL a[101010], b[101010], c[101010];

int main(){

// 1. 入力情報.

LL N;

int M;

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

map<LL, int> m;

rep(i, M){

scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);

m[a[i]] = 1;

m[b[i]] = 1;

}

m[1] = 1;

m[N] = 1;

// 2. 座標圧縮.

int idx = -1;

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

// 3. グラフ構築(階段).

LL cBef, cCur;

int vBef = -1, vCur;

for(auto &p : m){

// 今回分更新.

cCur = p.a;

vCur = p.b;

// 辺を追加.

if(vBef != -1){

G[vBef].pb(edge{vCur, cCur - cBef});

G[vCur].pb(edge{vBef, cCur - cBef});

}

// 前回分更新.

cBef = cCur;

vBef = vCur;

}

// 4. グラフ構築(エレベーター).

rep(i, M){

int u = m[a[i]];

int v = m[b[i]];

G[u].pb(edge{v, c[i]});

G[v].pb(edge{u, c[i]});

}

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

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

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

// 初期化.

priority_queue<edge> pq;

// 始点設定.

d[s] = 0;

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

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

while(!pq.empty()){

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

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 訪問済みフラグ設定.

if(memo[cn]) continue;

memo[cn]++;

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

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});

}

};

// 6. 各頂点までの, 最短コストを求める.

LL d[idx + 1]; // 頂点 0 からの距離.

int memo[idx + 1]; // 訪問済みフラグ.

rep(i, idx + 1) d[i] = INF, memo[i] = 0;

dijkstra(0, d, memo);

// 7. 出力.

printf("%lld\n", d[idx]);

return 0;

}

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

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

[入力例]
1000000000000000000 1
1 1000000000000000000 1000000000000000000

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

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

[出力例]
7

[入力例]
100 10
1 10 5
5 17 7
18 35 12
49 66 11
77 95 8
36 52 9
10 25 7
40 75 47
51 68 10
28 41 11

[出力例]
65

[入力例]
20220104 20
828865 4804632 12069969
6295187 13558375 1837197
3310273 11010080 7881068
5772550 14219264 18758563
4225815 8738497 6630771
6879164 10620764 10892637
4838718 8073754 14372199
6291069 10471126 70549
558133 1418658 9345163
8215556 18066689 18750539
8371221 8912288 13240335
6496981 12139308 15053771
7416355 12359442 7081448
116798 5578623 17894867
5948188 12066446 315682
932978 4289526 519795
3579073 9810527 15940312
8175707 15948535 19959019
4000956 6515736 2966577
8639132 11793341 15657568

[出力例]
11580774

[入力例]
202112111300 30
2836912071 8265759792 18349207920
6321404409 7117150178 5191319749
5133174124 6981490113 4115025861
8073790036 13562620650 576427819
2311345537 5346249323 15395778052
5232172781 6860771277 4967211588
9930875748 18298309556 1894862604
5493633256 9764925778 4529928865
2129123401 12177775551 771175460
6877686882 11695500319 16000522151
613446757 1219290120 8543162814
4425468693 6201308906 17815170784
760738956 10235609132 1569024502
5970087903 12676828451 5368533553
847837589 8203683049 654051583
3366379489 5918321181 16417033782
8019754324 14372671034 4782560986
10048397218 14291129034 14916272145
4180881599 8564813978 6154260194
8335300636 9618931292 7974820034
8247089832 17234489737 112903612
9226479498 12245429510 17492201072
584745120 5781270528 11323123105
1266934563 5758721472 12198029546
5226702368 8951155543 783723174
9715667921 18083960295 14479844635
5325151693 9867219235 787867457
4579272049 9781286327 1477152595
564092880 5096514264 17221220356
1621294237 11411345457 12861090392

[出力例]
186535821129

100

101

102

103

[入力例]

10 2

2 5 1

4 10 3

[出力例]

※AtCoderテストケースより

[入力例]

1000000000000000000 1

1 1000000000000000000 1000000000000000000

[出力例]

999999999999999999

※AtCoderテストケースより

[入力例]

11 3

2 4 1

5 7 1

8 10 1

[出力例]

[入力例]

100 10

1 10 5

5 17 7

18 35 12

49 66 11

77 95 8

36 52 9

10 25 7

40 75 47

51 68 10

28 41 11

[出力例]

[入力例]

20220104 20

828865 4804632 12069969

6295187 13558375 1837197

3310273 11010080 7881068

5772550 14219264 18758563

4225815 8738497 6630771

6879164 10620764 10892637

4838718 8073754 14372199

6291069 10471126 70549

558133 1418658 9345163

8215556 18066689 18750539

8371221 8912288 13240335

6496981 12139308 15053771

7416355 12359442 7081448

116798 5578623 17894867

5948188 12066446 315682

932978 4289526 519795

3579073 9810527 15940312

8175707 15948535 19959019

4000956 6515736 2966577

8639132 11793341 15657568

[出力例]

11580774

[入力例]

202112111300 30

2836912071 8265759792 18349207920

6321404409 7117150178 5191319749

5133174124 6981490113 4115025861

8073790036 13562620650 576427819

2311345537 5346249323 15395778052

5232172781 6860771277 4967211588

9930875748 18298309556 1894862604

5493633256 9764925778 4529928865

2129123401 12177775551 771175460

6877686882 11695500319 16000522151

613446757 1219290120 8543162814

4425468693 6201308906 17815170784

760738956 10235609132 1569024502

5970087903 12676828451 5368533553

847837589 8203683049 654051583

3366379489 5918321181 16417033782

8019754324 14372671034 4782560986

10048397218 14291129034 14916272145

4180881599 8564813978 6154260194

8335300636 9618931292 7974820034

8247089832 17234489737 112903612

9226479498 12245429510 17492201072

584745120 5781270528 11323123105

1266934563 5758721472 12198029546

5226702368 8951155543 783723174

9715667921 18083960295 14479844635

5325151693 9867219235 787867457

4579272049 9781286327 1477152595

564092880 5096514264 17221220356

1621294237 11411345457 12861090392

[出力例]

186535821129

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

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題I (直通エレベーター) を解いてみた.

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題I (直通エレベーター) を解いてみた.

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