[最短経路]フロイド

白峻11404号。/収録本
質問する
入力

第1行都市個数n

1<=n<=100

の2行目はバスの数m

1<=m<=100,000

3 3行目から、バス上の情報a(始発都市)、b(到着都市)、c(コスト.1<=c<=10000)

.

出力
出力

n行、

i行目に出力されるj数字は、都市iからjまでの最小コストである.iからjに至ることができない場合、その場出力

.
に答える
初見
FloydWarshareで1時から1時までの最小料金を求めます.
ソリューション
FloydWaterですが、AとBを結ぶ幹線が複数あるかもしれません.
最短の幹線情報のみを格納します.
時間の複雑さ
flowersalの時間複雑度はo(N^3)
コード#コード#

INF = int(1e9)

# 노드의 갯수 및 간선 갯수 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range (n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1) :
	for b in range(1, n+1) :
		if a == b :
			graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m) :
	# A에서 B로 가는 비용은 C라고 설정
	a, b, c = map(int, input().split())
	# 가장 짧은 간선 정보만 저장 #### 중복 간선은 최솟값만 저장한다!!! ####
	if c < graph[a][b] :
		graph[a][b] = c

# 점화식에 따라 플로이드워셜 알고리즘을 수행
for k in range(1, n+1) :
	for a in range(1, n+1) :
		for b in range(1, n+1) :
			graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과 출력
for a in range(1, n+1) :
	for b in range(1, n+1) :
		# 도달할 수 없는 경우, 0 출력
		if graph[a][b] = INF :
			print(0, end=" ")
		else :
			print(graph[a][b], end=" ")
	print()

に感銘を与える
フロイド・ウォーシェルはほとんど相変わらず!
重複幹線は最高価格しか貯蔵されていない.