[Baekjoon] 11404. フロイド[G 4]

📚 質問する

https://www.acmicpc.net/problem/11404

📖 に答える

最初はどうすればいいか考えていましたが、BFSナビゲーションでは重複値が多くて解決策が思いつきませんでした.そこで,答えを探すことでFloydwalshアルゴリズムを利用した問題を発見した.
floydwalshアルゴリズムを優先的に学習した.
すべての頂点で最短パスを求めるときに使用されるアルゴリズム.
floydwalshアルゴリズムは,頂点数が少なく,幹線数が多い場合に用いられる.
O(n^3)ですが、nは100なので、n^3は100万くらいになります.
FloyWarshアルゴリズムの概要
注意:https://blog.naver.com/ndb796/221234427842
頂点は2 D配列で、y軸は開始頂点、x軸は到達頂点であり、値には費用の最大値が含まれます.
これは問題を含む直接費用です.
問題(開始ノード、到達ノード)が重複する可能性があるため、コストの最大値とします.
直通車がなければ、後で最高価格が加算されるので、その価格より高い価格が加算されます.
100000は費用で、最大経路なら100箇所まで加算でき、100000*100になります.
通過する頂点を選択します.
頂点を選択する順序は、関連するXですが、すべての頂点を選択するには、昇順で選択します.
選択した頂点をXと呼ぶ場合は、選択した頂点を通過する必要があります.したがって、開始点と終了点はXとは異なる必要があります.
ex). A->X,X->BのA,BはXとは異なり通過する.
経過時の費用と経過していない費用を比較して、最高の価格を出します.
すべての頂点を比較すると、コストの最大値に更新されます.
行けない場合は1000000を初期値とし、この場合のみ0に変換して出力します.

📒 コード#コード#

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
arr = [[10000000]*(n + 1) for _ in range(n + 1)]
for _ in range(m):
    s, e, fee = map(int, input().split())
    arr[s][e] = min(arr[s][e], fee)

# 플로이드 와샬 알고리즘 이용!
for k in range(1, n + 1):           # 정점을 순차적으로 수행
    for i in range(1, n + 1):
        if k == i:
            continue
        for j in range(1, n + 1):
            if k == j or i == j:    # 경유해야하니 정점이 달라야 한다.
                continue
            arr[i][j] = min(arr[i][j], arr[k][j] + arr[i][k])   # 경유할 때와 현재 값과 비교

for i in range(1, n + 1):   # 10000000을 0으로 변경
    for j in range(1, n + 1):
        if arr[i][j] == 10000000:
            arr[i][j] = 0

for i in range(1, n + 1):
    print(*arr[i][1:])

🔍 結果