[これがコードテストです]最短距離フロイド

最短距離アルゴリズム

マルチアウトレットアルゴリズム
1つのアルゴリズム

は、グラフィックに複数のノードがある場合、1つのノードから別のノードへの各最短経路を解く.

流水アルゴリズム

、すべての場所から他のすべての場所への最短パスが必要な場合

ベルマンフォードアルゴリズム

白峻11404号.
に質問
n(1<=n<=100)都市、ある都市から別の都市に到着するm(1<=m<=10000)バス.各バスには、一度に使用するために必要なコストがあります.各都市の一対(A,B)のためにプログラムを作成し,都市AからBまでに必要な最高コストを求める.
1行目の都市数n
2行目のバス数m
3行目からm+2行、バスの起点都市a、終点都市bまで、1回の乗車に必要な料金c.都市と到着都市は同じ状況ではない.
開始都市と到着都市を結ぶルートは1つだけではないかもしれません.
入力例
5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4
出力例
0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0
💻 コード#コード#

import sys

input = sys.stdin.readline

INF = int(1e9)

n = int(input())  # 도시의 개수
m = int(input())  # 버스의 개수

graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 버스 노선이 같다면 비용이 최솟값인 값 저장
for _ in range(m):
    a, b, c = map(int, input().split())
    if graph[a][b] != INF:
        graph[a][b] = min(graph[a][b], c)
    else:
        graph[a][b] = c
    # if c < graph[a][b]:
    #    graph[a][b] = c

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0

for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])


for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] == INF:
            print(0, end = " ")
        else:
            print(graph[i][j], end = " ")
    print()

デザイン
floydwalshアルゴリズムを用いて容易に解決した.
📝 整理する
バス路線が同じであるため、より小さな料金を格納するためにmin 함수を使用せず、if c < graph[i][j]: graph[i][j] = cとより容易に解くことができる.最近はmin関数がよく使われているので、おなじみのものしか考えられず、新しい方法は考えられませんでした.