2022.03.01 TIL

https://www.acmicpc.net/problem/1956
1956号問題
質問する
Vの村とEの道路からなる都市があります.道は村と村の間にあり、一方通行です.村のコンビニ1番からV番まで番号があります.
道路に沿ってトレーニングの道を見つけたいです.運動後はスタート地点に戻ったほうがいいので、周期を見つけたいです.しかし、あなたは運動が嫌いなので、道の長さの和を最小にしたいと思っています.
道路情報を取得する場合は、道路の長さの和の最小周期を検索するプログラムを作成します.2つの村を往復する場合も自転車に含めて注意が必要です.
熟考の末、自ら作成してエラー処理を確認し、エラーの部分を探し出し、称後、最小値更新に関するアルゴリズムが欠けていることを発見し、floydとshallアルゴリズムを使用すべきであることを知った.floydとshallアルゴリズムとこの問題の成功解を理解した.
floydとshallアルゴリズム
floydとshallアルゴリズムの核心は,点から点までの距離の初期値と経路を通る距離を比較することによって最小値を導出し,その後繰り返し続け,すべての点間の最小距離を更新することである.自分で描いた絵で説明して理解してみました.

これらの点が関係しているなら、
1番支点2番支点3番支点4番支点1番支点inf 23 inf 2番支点infnf 153番支点inf 2 infnf 4番支点3 infnf
一度経由して、初めて整理すると、
1番支点2番支点3番支点4番支点1番支点inf 2572番支点83153番支点inf 2374番支点358 inf
同じ方法でもう一度来ます.
1号地点2号地点3号地点4号地点1号地点102572号地点83153号地点102374号地点35810
この方法で経路経由で最小経路のアルゴリズムを更新する.これをJavaと表示すると、

for(int i = 1; i <= v; i++){
            for(int j = 1; j <= v; j++){
                for(int k = 1; k <= v; k++){
                    if(arr[j][k] > arr[j][i] + arr[i][k]){
                        arr[j][k] = arr[j][i] + arr[i][k];
                    }
                }
            }
        }

このように,始点i,経路k,到達点,jの3つのfor反復文を経て,修正後に行う.この方法で1−>12−>23−>3等の戻りサイクルの最小値を得た後,戻る運動サイクルの距離は出発村毎に最小値を求め,その最小値を村毎の距離から出力することができる.
Reference
https://blog.naver.com/ndb796/221234427842
https://dragon-h.tistory.com/27
https://dragon-h.tistory.com/23