BOJ::宅配便(No.1719)

質問する
明宇企業は2008年から宅配業務を新設することを決めた.まずいくつかのコンテナポイントを用意して宅配貨物を処理したが、宅配貨物が各コンテナポイント間を往復する経路は決められなかった.どのパスを通過するかを決定し、パステーブルに整理するのは皆さんがしなければならないことです.
例図中の太字表示の1、2、3、4、5、6は集合キャビネットを示す.頂点間の幹線は、2つのコンテナ間の貨物が移動可能であることを示し、重み付けは移動に要する時間である.パステーブルは次のとおりです.
ルーティングテーブルは、あるコンテナポイントから別のコンテナポイントへの最短経路で貨物を移動するために、まず通過するコンテナポイントを示す.例えば、4行5列目の6は、4番目の集鉱場から5番目の集鉱場まで最短経路を通過するには、まず6番目の集鉱場に移動することを意味する.
類似のパステーブルを得るためにプログラムを作成してください.
入力
第1行の2つの数nとmは、スペースを隔てて順次与えられる.nは集合場の個数,200以下の自然数,mは集合場間経路の個数,10000以下の自然数である.次に、1行に1つのセットから別のセットへのパスが1つずつ与えられ、2つのセットの番号と往復の間に必要な時間が順次与えられる.集合点の番号とパスの所要時間が1000以下の自然数です.
しゅつりょく
サンプルと同じフォーマットのパステーブルを出力します.
の意見を打診
これがダエストラの問題だと知っているので、ダエストラを使いたいです.

しかし、問題を見ると、n:nで最短経路を探すべきだ.

に従って、Floyd-Warshallとします.

セグメントは最短経路を探すのではなく、最初の集合点を探す問題であるため、

また記録

の初回の並びを作成する.

Solution 1

import sys
input = sys.stdin.readline

def init():
    for _ in range(m):
        src, dst, weight = map(int, input().split())
        graph[src][dst] = graph[dst][src] = weight
        ans[src][dst] = dst
        ans[dst][src] = src


def present():
    for nums in ans[1:]:
        print(*nums[1:])

def floydWarshall():
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                if i == j: continue
                result = graph[i][k] + graph[k][j]
                if graph[i][j] <= result: continue

                graph[i][j] = graph[j][i] = result
                ans[i][j], ans[j][i] = ans[i][k], ans[j][k]

def solve():
    init()
    floydWarshall()
    present()
 
n,m = map(int, input().split())
graph = [[1e9]*(n+1) for _ in range(n+1)]
ans = [["-"]*(n+1) for _ in range(n+1)]

solve()