白駿11404号:フロイド

8137 ワード
python ps floyd テキストリンク

りゅうたい


白駿11404号:フロイド

アイデア


N*Nサイズの並びに費用を格納します.(r,c)は、r番ノードからc番ノードへのコストを含む.
(1,1)から(N,N)に移動し,iノードを通過した場合,よりコストが小さくなると更新する.
三重複文を使用する場合は、一番上の複文からいくつ目のノードを通るかを指定する必要があります.

コード#コード#

import sys
input = sys.stdin.readline
INF = 987654321
N = int(input())
M = int(input())

dist = [[INF] * (N + 1) for _ in range(N + 1)]

for idx in range(N + 1):
    dist[idx][idx] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    dist[a][b] = min(dist[a][b], c)

for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            # j -> k vs j -> i -> k 뭐가 더 빠를까?
            dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

for r in range(1, N + 1):
    for c in range(1, N + 1):
        if dist[r][c] == INF:
            print(0, end=' ')
        else:
            print(dist[r][c], end=' ')
    print()

おしゃべり


繰り返し文順序主義
[BOJ 4195]友達ネットワーク(Java)
DB timezone Value error