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

C++の練習を兼ねて, AtCoder Regular Contest 061 の問題E (すぬけ君の地下鉄旅行) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 問題Eは, ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 拡張グラフ構築に, 非常に苦労したものの, TLE版を回避する実装まで, 持って行けたので, 及第点は取れたと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/061/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
using vvp = vector<vp>;
using PQ = priority_queue<P, vp, greater<P>>;
#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 int INF = 1010101010;

struct edge{
    int n; // 次の駅.
    int c; // 会社情報.
    bool operator < (const edge &E) const{ return c > E.c; }
};

vector<edge> G[101010];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    map<P, int> m;
    rep(i, M){
        int p, q, c;
        scanf("%d %d %d", &p, &q, &c);
        --p;
        --q;
        G[p].pb(edge{q, c});
        G[q].pb(edge{p, c});
        
        // (現在いる駅, 最後に使った会社) と見なして, 保存.
        m[{p, c}] = 0;
        m[{q, c}] = 0;
    }
    
    // 2. (現在いる駅, -1) を 保存.
    rep(i, N) m[{i, -1}] = 0;
    
    // 3. 座標圧縮.
    // -> 拡張グラフの頂点番号を保存.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 4. 拡張グラフ構築.
    // -> set<edge> を利用すると, 期待した辺が追加されなかったため却下.
    // -> set<pair<int, int>> は, 問題なさそうだったが, いったん却下.
    // -> pair<int, int> の 第一成分: 移動コスト, 第二成分: (拡張グラフの)頂点 と 読み替える.
    vvp GX(idx + 1);
    rep(i, N){
        // (現在いる駅, 最後に使った会社) は, 駅 i から 駅 cur.n の 区間で考える.
        // -> 駅 i にいた場合, 前回利用した会社 と 同じ or 異なる の 二通りの可能性があるので, 
        //    両方とも拡張グラフに埋め込んでおくようにする.
        for(auto &cur : G[i]){
            int cn = cur.n;
            int cc = cur.c;
            
            // 同じ会社に乗り換えるケース.
            GX[m[{i, cc}]].pb({0, m[{cn, cc}]});
            
            // 違う会社に乗り換えるケース(改札から外に出る).
            GX[m[{i, cc}]].pb({0, m[{i, -1}]});
            
            // 改札に入る.
            GX[m[{i, -1}]].pb({1, m[{cn, cc}]});
        }
    }
    
    // 5. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, int* d, int* memo){
        // 初期化.
        PQ pq;
        
        // 始点設定.
        d[s] = 0;
        pq.push({0, s});
        
        // キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 今回分(拡張グラフ頂点).
            P e = pq.top();
            pq.pop();
            int cn = e.b;
            int cc = e.a;
            
            // 訪問済みフラグ設定(頂点ベース).
            if(memo[cn]) continue;
            ++memo[cn];
            
            // 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : GX[cn]){
                // 次回分(拡張グラフ頂点).
                int nn = g.b;
                int nc = cc + g.a;
                
                // 移動コスト更新.
                if(d[nn] > nc){
                    d[nn] = nc;
                    pq.push({nc, nn});
                }
            }
        }
    };
    int memo[idx + 1], d[idx + 1];
    rep(i, idx + 1){
        memo[i] = 0;
        d[i] = INF;
    }
    dijkstra(m[{0, -1}], d, memo);
    
    // 6. 出力.
    printf("%d\n", (d[m[{N - 1, -1}]] == INF) ? -1 : d[m[{N - 1, -1}]]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

// 解き直し.

// https://img.atcoder.jp/data/arc/061/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

using vvp = vector<vp>;

using PQ = priority_queue<P, vp, greater<P>>;

#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 int INF = 1010101010;

struct edge{

int n; // 次の駅.

int c; // 会社情報.

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

};

vector<edge> G[101010];

int main(){

// 1. 入力情報.

int N, M;

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

map<P, int> m;

rep(i, M){

int p, q, c;

scanf("%d %d %d", &p, &q, &c);

--p;

--q;

G[p].pb(edge{q, c});

G[q].pb(edge{p, c});

// (現在いる駅, 最後に使った会社) と見なして, 保存.

m[{p, c}] = 0;

m[{q, c}] = 0;

}

// 2. (現在いる駅, -1) を保存.

rep(i, N) m[{i, -1}] = 0;

// 3. 座標圧縮.

// -> 拡張グラフの頂点番号を保存.

int idx = -1;

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

// 4. 拡張グラフ構築.

// -> set<edge> を利用すると, 期待した辺が追加されなかったため却下.

// -> set<pair<int, int>> は, 問題なさそうだったが, いったん却下.

// -> pair<int, int> の第一成分: 移動コスト, 第二成分: (拡張グラフの)頂点と読み替える.

vvp GX(idx + 1);

rep(i, N){

// (現在いる駅, 最後に使った会社) は, 駅 i から駅 cur.n の区間で考える.

// -> 駅 i にいた場合, 前回利用した会社と同じ or 異なるの二通りの可能性があるので,

// 両方とも拡張グラフに埋め込んでおくようにする.

for(auto &cur : G[i]){

int cn = cur.n;

int cc = cur.c;

// 同じ会社に乗り換えるケース.

GX[m[{i, cc}]].pb({0, m[{cn, cc}]});

// 違う会社に乗り換えるケース(改札から外に出る).

GX[m[{i, cc}]].pb({0, m[{i, -1}]});

// 改札に入る.

GX[m[{i, -1}]].pb({1, m[{cn, cc}]});

}

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

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

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

// 初期化.

PQ pq;

// 始点設定.

d[s] = 0;

pq.push({0, s});

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

while(!pq.empty()){

// 今回分(拡張グラフ頂点).

P e = pq.top();

pq.pop();

int cn = e.b;

int cc = e.a;

// 訪問済みフラグ設定(頂点ベース).

if(memo[cn]) continue;

++memo[cn];

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

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

// 次回分(拡張グラフ頂点).

int nn = g.b;

int nc = cc + g.a;

// 移動コスト更新.

if(d[nn] > nc){

d[nn] = nc;

pq.push({nc, nn});

}

};

int memo[idx + 1], d[idx + 1];

rep(i, idx + 1){

memo[i] = 0;

d[i] = INF;

}

dijkstra(m[{0, -1}], d, memo);

// 6. 出力.

printf("%d\n", (d[m[{N - 1, -1}]] == INF) ? -1 : d[m[{N - 1, -1}]]);

return 0;

}

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

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

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

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

[入力例]
2 0

[出力例]
-1
※AtCoderのテストケースより

[入力例]
2 1
1 2 3

[出力例]
1

[入力例]
3 1
1 2 3

[出力例]
-1

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

[出力例]
1

[入力例]
10 14
1 4 1
1 3 2
1 2 3
4 3 1
3 6 5
4 8 2
2 5 4
5 6 4
6 8 2
6 6 6
5 7 5
7 10 6
8 9 3
9 10 4

[出力例]
4

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

[出力例]
3

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

[出力例]
5

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

[入力例]

3 3

1 2 1

2 3 1

3 1 2

[出力例]

※AtCoderのテストケースより

[入力例]

8 11

1 3 1

1 4 2

2 3 1

2 5 1

3 4 3

3 6 3

3 7 3

4 8 4

5 6 1

6 7 5

7 8 5

[出力例]

※AtCoderのテストケースより

[入力例]

2 0

[出力例]

-1

※AtCoderのテストケースより

[入力例]

2 1

1 2 3

[出力例]

[入力例]

3 1

1 2 3

[出力例]

-1

[入力例]

3 3

2 3 2

1 2 1

1 3 3

[出力例]

[入力例]

10 14

1 4 1

1 3 2

1 2 3

4 3 1

3 6 5

4 8 2

2 5 4

5 6 4

6 8 2

6 6 6

5 7 5

7 10 6

8 9 3

9 10 4

[出力例]

[入力例]

15 22

1 2 1

1 3 3

2 8 2

8 9 2

9 2 1

7 9 1

2 10 2

10 6 2

7 6 2

7 13 2

13 12 5

6 12 4

6 5 4

5 12 4

12 15 5

15 11 5

11 5 4

5 4 3

11 4 1

4 14 1

4 3 3

14 3 1

[出力例]

[入力例]

20 30

1 6 1

1 5 1

2 1 3

6 7 2

8 7 3

8 5 2

8 9 3

5 3 4

2 4 5

3 4 2

9 3 6

9 10 1

4 10 2

4 13 2

10 12 1

10 14 1

13 14 1

15 14 1

15 12 2

11 12 2

11 9 4

9 16 2

16 17 3

17 20 5

11 17 2

12 18 1

18 17 2

18 19 1

15 19 2

19 20 3

[出力例]

■参照サイト
AtCoder Regular Contest 061

C++の練習を兼ねて, AtCoder Regular Contest 061 の 問題E (すぬけ君の地下鉄旅行) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 061 の問題E (すぬけ君の地下鉄旅行) を解いてみた.

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