๋ฌธ์
https://www.acmicpc.net/problem/11404
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x1C๊ฐ - ํ๋ก์ด๋ ์๊ณ ๋ฆฌ์ฆ
์๊ณ ๋ฆฌ์ฆ: ์ต๋จ ๊ฒฝ๋ก, ํ๋ก์ด๋-์์
ํ์ด

์ ๋ง ๊ธฐ์ด์ ์ธ ํ๋ก์ด๋ ์์ ๋ฌธ์ ๋ค.
ํ๋ก์ด๋-์์ ์๊ณ ๋ฆฌ์ฆ?
์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋๋ฐ์ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ ์ค ํ๋๋ค. (+ ๋ค์ต์คํธ๋ผ, ๋ฒจ๋ง-ํฌ๋)
๋ค๋ฅธ ๋ ๊ฐ๋ ํ ์ ์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ์ง๋ง, ํ๋ก์ด๋ ์์
์ ๋ชจ๋ ์ ์ ์ ๊ฐ์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ํ๋ฒ์ ๊ณ์ฐํ๋ค. (๊ทธ๋ฆฌ๊ณ ์์ ๊ฐ์ค์น๋ ๊ณ์ฐ ๊ฐ๋ฅ)
์๋ฆฌ๋ DP์ ๋น์ทํ๋ค.
์ ์ i์์ ์ ์ j๋ก ๊ฐ๋ ๊ฒฝ๋ก ์ค,์ ์ k๋ฅผ ๊ฒฝ์ ํ๋ ๊ฒฝ๋ก๊ฐ ๋ ์งง๋ค๋ฉด ๐ ์ต๋จ ๊ฒฝ๋ก ๊ฐฑ์
for k in range(N):
for i in range(N):
for j in range(N):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
๊ทธ๋ฆฌ๊ณ ๋ชจ๋ ์ ์ k์ ๋ํด ์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ฉด์ ๊ฐฑ์ ํด๋๊ฐ๋ค.
์ ์ฒด ์ฝ๋
# ์ต๋จ ๊ฒฝ๋ก
# ํ๋ก์ด๋-์์
์๊ณ ๋ฆฌ์ฆ ๋ฌธ์
# ํ ๋
ธ๋์์ ๋ชจ๋ ๋
ธ๋๊น์ง๊ฐ ์๋, ๋ชจ๋ ๋
ธ๋๊ฐ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ ์ ์๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
# ์์๋
ธ๋๊ฐ i, ๋์ฐฉ๋
ธ๋๊ฐ j์ผ๋ ๋
ธ๋ k๋ฅผ ๊ฑฐ์ณ๊ฐ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ธํ๋ค. dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
# ๋ฉ๋ชจ๋ฆฌ: 42140KB / ์๊ฐ: 376ms
from sys import stdin
input = stdin.readline
INF = int(1e9)
n = int(input())
N = n + 1
m = int(input())
bus = []
for _ in range(m):
bus.append(tuple(map(int, input().split())))
def floyd_warshall():
dp = [[INF]*(N) for _ in range(N)]
for i in range(1, N): # ์๊ธฐ ์์ ์ผ๋ก ๊ฐ๋ ๋น์ฉ์ 0์ผ๋ก ์ค์ ํ๋ค.
dp[i][i] = 0
for u, v, w in bus: # ์์-๋์ด ๊ฐ์ ๋
ธ์ ์ด ์ฌ๋ฌ ๊ฐ ์์ ์ ์๊ธฐ ๋๋ฌธ์ ์ต์๊ฐ์ธ ๋
ธ์ ์ผ๋ก ์ค์ ํ๋๋ก ํ๋ค.
dp[u][v] = min(dp[u][v], w)
for k in range(1, N): # ๊ฑฐ์น๋ ๋ถ๋ถ
for i in range(1, N): # ์์์
for j in range(1, N): # ๋์
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
return dp
ret = floyd_warshall()
for i in range(1, N):
for j in range(1, N):
if ret[i][j] == INF:
ret[i][j] = 0
print(*ret[i][1:])