문제

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

Input)
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
Output)
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

Point

플로이드 워셜

• 모든 1~n범위의 k, i, j에 대해,
  ( dist[i][k] + dist[k][j] )와 ( dist[i][j] )의 값 비교를 통해
  최소값을 update한다.

노드간 여러개의 간선

• 플로이드 워셜을 활용해야 하는 문항은 간선의 개수가 많은 경우다
• 그러므로 같은 두 개의 노드 사이에 다른 가중치를 가진 간선이 여러개 있도록 주어지는 경우가 대부분
• 최소 비용 -> 가중치가 최소인 간선만 저장한다.

정수 최대값 최소값

• 최소값을 찾을 경우 변수 초기화를 최대값으로 해야 한다.
• 1e9 : float 타입

# 10억 이내 범위에서 최대값
INF = int(1e9)
INF = int(-1e9)
# int범위 내 최대값
INF = int(2e9)

전체코드

INF = int(1e9)
n = int(input())
m = int(input())

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

for _ in range(m):
  a, b, c = [int(x) for x in input().split()]
  if c < cost[a][b]:
    cost[a][b] = c

for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      if i == j:
        cost[i][j] = 0
        continue
      if cost[i][k] == INF or cost[k][j]==INF:
        continue
      if cost[i][k]+cost[k][j] < cost[i][j]:
        cost[i][j] = cost[i][k]+cost[k][j]

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