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

C++の練習を兼ねて, SoundHound Inc. Programming Contest 2018 -Masters Tournament- の問題D (Saving Snuuk) を解いてみた.

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

本家のサイト SoundHound Inc. Programming Contest 2018 -Masters Tournament- 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/soundhound2018-summer-qual/editorial.pdf
// 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; }
};

int main(){
    
    // 1. 入力情報.
    int N, M, s, t;
    scanf("%d %d %d %d", &N, &M, &s, &t);
    --s, --t;
    vector<vector<edge>> GY(N), GS(N);
    rep(i, M){
        int u, v, a, b;
        scanf("%d %d %d %d", &u, &v, &a, &b);
        u--;
        v--;
        
        // グラフ(円ベース).
        GY[u].pb(edge{v, (LL)a});
        GY[v].pb(edge{u, (LL)a});
        
        // グラフ(スヌークベース).
        GS[u].pb(edge{v, (LL)b});
        GS[v].pb(edge{u, (LL)b});
    }
    
    // 2. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](vector<vector<edge>> &G, 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. 最小コスト計算.
    // 3-1. 都市 s から, 各都市までの, 最小コスト(円).
    LL dy[N];
    int memo[N];
    rep(i, N) dy[i] = INF, memo[i] = 0;
    dijkstra(GY, s, dy, memo);
    
    // 3-2. 都市 t から, 各都市までの, 最小コスト(スヌーク).
    LL ds[N];
    rep(i, N) ds[i] = INF, memo[i] = 0;
    dijkstra(GS, t, ds, memo);
    
    // 4. 最小コストを保存.
    LL ans[N + 1];
    rep(i, N) ans[i + 1] = INF;
    repr(i, N - 1, 0) ans[i] = min(ans[i + 1], dy[i] + ds[i]);
    
    // 5. 出力.
    rep(i, N) printf("%lld\n", 1000000000000000 - ans[i]);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/soundhound2018-summer-qual/editorial.pdf

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

};

int main(){

// 1. 入力情報.

int N, M, s, t;

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

--s, --t;

vector<vector<edge>> GY(N), GS(N);

rep(i, M){

int u, v, a, b;

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

u--;

v--;

// グラフ(円ベース).

GY[u].pb(edge{v, (LL)a});

GY[v].pb(edge{u, (LL)a});

// グラフ(スヌークベース).

GS[u].pb(edge{v, (LL)b});

GS[v].pb(edge{u, (LL)b});

}

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

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

auto dijkstra = [&](vector<vector<edge>> &G, 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. 最小コスト計算.

// 3-1. 都市 s から, 各都市までの, 最小コスト(円).

LL dy[N];

int memo[N];

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

dijkstra(GY, s, dy, memo);

// 3-2. 都市 t から, 各都市までの, 最小コスト(スヌーク).

LL ds[N];

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

dijkstra(GS, t, ds, memo);

// 4. 最小コストを保存.

LL ans[N + 1];

rep(i, N) ans[i + 1] = INF;

repr(i, N - 1, 0) ans[i] = min(ans[i + 1], dy[i] + ds[i]);

// 5. 出力.

rep(i, N) printf("%lld\n", 1000000000000000 - ans[i]);

return 0;

}

[入力例]
4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1

[出力例]
999999999999998
999999999999989
999999999999979
999999999999897
※AtCoderテストケースより

[入力例]
8 12 3 8
2 8 685087149 857180777
6 7 298270585 209942236
2 4 346080035 234079976
2 5 131857300 22507157
4 8 30723332 173476334
2 6 480845267 448565596
1 4 181424400 548830121
4 5 57429995 195056405
7 8 160277628 479932440
1 6 475692952 203530153
3 5 336869679 160714712
2 7 389775999 199123879

[出力例]
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994

[入力例]
6 9 3 6
1 2 7 26
1 3 28 61
1 5 28 78
2 4 33 36
2 6 35 111
3 4 58 20
3 6 110 62
4 5 119 113
5 6 99 93

[出力例]
999999999999938
999999999999938
999999999999938
999999999999930
999999999999930
999999999999930

[入力例]
13 16 1 10   
1 3 83326247 85207902
2 6 88459189 47559762
3 4 64979941 49458276
3 6 63050768 74818459
6 7 72892460 34724650
4 5 77540583 1933897
7 8 67206752 87368224
5 8 65826188 61074237
5 9 33789592 14993064
5 13 117663151 108601936
8 10 119290100 121202962
8 12 28834706 29690680
9 11 4714256 35620023
10 11 69922693 6093865
11 12 69593125 40027289
11 13 85863036 57212982

[出力例]
999999808574628
999999808574628
999999808574628
999999793052963
999999729555516
999999729555516
999999729555516
999999729555516
999999729555516
999999729555516
999999729555516
999999638567913
999999593183231

[入力例]

4 3 2 3

1 4 1 100

1 2 1 10

1 3 20 1

[出力例]

999999999999998

999999999999989

999999999999979

999999999999897

※AtCoderテストケースより

[入力例]

8 12 3 8

2 8 685087149 857180777

6 7 298270585 209942236

2 4 346080035 234079976

2 5 131857300 22507157

4 8 30723332 173476334

2 6 480845267 448565596

1 4 181424400 548830121

4 5 57429995 195056405

7 8 160277628 479932440

1 6 475692952 203530153

3 5 336869679 160714712

2 7 389775999 199123879

[出力例]

999999574976994

[入力例]

6 9 3 6

1 2 7 26

1 3 28 61

1 5 28 78

2 4 33 36

2 6 35 111

3 4 58 20

3 6 110 62

4 5 119 113

5 6 99 93

[出力例]

999999999999938

999999999999930

[入力例]

13 16 1 10

1 3 83326247 85207902

2 6 88459189 47559762

3 4 64979941 49458276

3 6 63050768 74818459

6 7 72892460 34724650

4 5 77540583 1933897

7 8 67206752 87368224

5 8 65826188 61074237

5 9 33789592 14993064

5 13 117663151 108601936

8 10 119290100 121202962

8 12 28834706 29690680

9 11 4714256 35620023

10 11 69922693 6093865

11 12 69593125 40027289

11 13 85863036 57212982

[出力例]

999999808574628

999999793052963

999999729555516

999999638567913

999999593183231

■参照サイト
SoundHound Inc. Programming Contest 2018 -Masters Tournament-

C++の練習を兼ねて, SoundHound Inc. Programming Contest 2018 -Masters Tournament- の 問題D (Saving Snuuk) を解いてみた.

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

C++の練習を兼ねて, SoundHound Inc. Programming Contest 2018 -Masters Tournament- の問題D (Saving Snuuk) を解いてみた.

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