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

C++の練習を兼ねて, AtCoder Beginner Contest 143 の問題E (E – Travel by Car) を解いてみた.

■感想.
1. ワーシャル–フロイド法を使って解くように見えたが, その先の方針が, 全然見えなかったので, 解説を確認した.
2. 解説で, ワーシャル–フロイド法を、二回使って解く方針が紹介されているが, これで解けてしまうことが摩訶不思議に思えた.
※ おそらく, 最短距離が, L以下の町の組に, 距離1 の辺を張るという部分を, よく理解する必要があると思った.

本家のサイトABC 143解説をご覧下さい.

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

// 解き直し.
// ABC 143解説.
// https://img.atcoder.jp/abc143/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int MAX = 301;
const LL INF = 1234567654321;
LL d1[MAX][MAX], d2[MAX][MAX];

int main(){
    
    // 1. 入力情報取得.
    int N, M, a, b;
    LL L, c;
    scanf("%d %d %lld", &N, &M, &L);
    for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) if(i != j) d1[i][j] = INF, d2[i][j] = INF;
    for(int i = 0; i < M; i++){
        scanf("%d %d %lld", &a, &b, &c);
        a--, b--;
        d1[a][b] = c;
        d1[b][a] = c;
    }
    
    // 2. ワーシャル–フロイド法(※各町間の最短距離を保存).
    for(int k = 0; k < N; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                d1[i][j] = min(d1[i][j], d1[i][k] + d1[k][j]);
            }
        }
    }
    
    // 3. 解説通り.
    // 3-1. 最短距離が, L以下の町の組に, 距離1 の 辺を張る(※もう一つグラフを作成).
    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) if(d1[i][j] <= L) d2[i][j] = 1;
    
    // 3-2. ワーシャル–フロイド法(※各町間を移動するときの燃料補給回数を保存).
    for(int k = 0; k < N; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);
            }
        }
    }
    
    // 4. Q個のクエリに回答.
    int Q, s, t;
    scanf("%d", &Q);
    for(int i = 0; i < Q; i++){
        scanf("%d %d", &s, &t);
        s--, t--;
        if(d2[s][t] == INF) printf("%d\n", -1);
        else                printf("%d\n", d2[s][t] - 1);
    }
    return 0;
    
}

// 解き直し.

// ABC 143解説.

// https://img.atcoder.jp/abc143/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int MAX = 301;

const LL INF = 1234567654321;

LL d1[MAX][MAX], d2[MAX][MAX];

int main(){

// 1. 入力情報取得.

int N, M, a, b;

LL L, c;

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

for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) if(i != j) d1[i][j] = INF, d2[i][j] = INF;

for(int i = 0; i < M; i++){

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

a--, b--;

d1[a][b] = c;

d1[b][a] = c;

}

// 2. ワーシャル–フロイド法(※各町間の最短距離を保存).

for(int k = 0; k < N; k++){

for(int i = 0; i < N; i++){

for(int j = 0; j < N; j++){

d1[i][j] = min(d1[i][j], d1[i][k] + d1[k][j]);

}

// 3. 解説通り.

// 3-1. 最短距離が, L以下の町の組に, 距離1 の辺を張る(※もう一つグラフを作成).

for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) if(d1[i][j] <= L) d2[i][j] = 1;

// 3-2. ワーシャル–フロイド法(※各町間を移動するときの燃料補給回数を保存).

for(int k = 0; k < N; k++){

for(int i = 0; i < N; i++){

for(int j = 0; j < N; j++){

d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);

}

// 4. Q個のクエリに回答.

int Q, s, t;

scanf("%d", &Q);

for(int i = 0; i < Q; i++){

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

s--, t--;

if(d2[s][t] == INF) printf("%d\n", -1);

else printf("%d\n", d2[s][t] - 1);

}

return 0;

}

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

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

[入力例]
4 0 1
1
2 1

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

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

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

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

[出力例]
2
1
1
-1
0

[入力例]

3 2 5

1 2 3

2 3 3

3 2

1 3

[出力例]

※AtCoderテストケースより

[入力例]

4 0 1

2 1

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 4 4

1 2 2

2 3 2

3 4 3

4 5 2

2 1

3 1

4 1

5 1

1 2

3 2

4 2

5 2

1 3

2 3

4 3

5 3

1 4

2 4

3 4

5 4

1 5

2 5

3 5

4 5

[出力例]

※AtCoderテストケースより

[入力例]

5 7 8

2 5 9

3 5 10

1 2 11

2 4 5

4 3 10

4 1 8

2 3 7

1 3

2 1

3 4

1 5

2 3

[出力例]

-1

■参照サイト
AtCoder Beginner Contest 143

C++の練習を兼ねて, AtCoder Beginner Contest 143 の 問題E (E – Travel by Car) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 143 の問題E (E – Travel by Car) を解いてみた.

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