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

์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํด์ผ ํ๋ ํ๋ก์ด๋ ์์
์ ํ์๊ณ , ์ถ๊ฐ๋ก ๊ฒฝ๋กํ(๋ค์์ ๋ฐฉ๋ฌธํ ๋
ธ๋)๋ ๊ตฌํด์ผ ํ๋ค.
(11780: ํ๋ก์ด๋ 2๋ฅผ ํ์ด๋ดค๋ค๋ฉด ์ฌ์ด ๋ฌธ์ ๋ค.)
๋จผ์ ์ต๋จ๊ฒฝ๋ก์ฉ ๋ฆฌ์คํธ / ๊ฒฝ๋ก ์ ์ฅ์ฉ ๋ฆฌ์คํธ๋ฅผ ๋ฐ๋ก ์์ฑํด์ผ ํ๋ค.
๊ฐ ๋ฆฌ์คํธ๋ ๋ค์๊ณผ ๊ฐ์ด ๊ตฌ์ฑ ๋ ์์ ์ด๋ค.graph[a][b]: a์์ b๋ก ๊ฐ๋ ์ต๋จ๊ฑฐ๋ฆฌnxt[a][b]: a์์ b๋ก ๊ฐ ๋, a ๋ค์์ผ๋ก ๋ฐฉ๋ฌธํ ๋
ธ๋
(a, b)๊ฐ ๊ฐ์ ์ค๋ณต ๋ฐ์ดํฐ๋ ์ฃผ์ด์ง์ง ์์ผ๋ ์ ๋ ฅ ๋ฐ์ดํฐ ๊ทธ๋๋ก ๋ฆฌ์คํธ์ ์ ์ฅํด์ฃผ๋ฉด ๋๋ค.
graph[a][b] = c
nxt[a][b] = b
๊ทธ๋ฆฌ๊ณ ํ๋ก์ด๋ ์์
์ ์ํํ๋ฉด์ ๊ฒฝ๋กํ๋ฅผ ๊ฐฑ์ ํด์ค๋ค.
๋ง์ฝ a-b ๋ฃจํธ๋ณด๋ค a-k + k-b ๋ฃจํธ๊ฐ ๋ ํจ์จ์ ์ด๋ผ๋ฉด a ๋ค์์ nxt[a][k] ๋
ธ๋๋ก ๊ฐ์ผ ํ๋ค.
if graph[a][b] > graph[a][k] + graph[k][b]:
graph[a][b] = graph[a][k] + graph[k][b]
nxt[a][b] = nxt[a][k]
์ด๋ฐ์์ผ๋ก ๊ฐฑ์ ํ๋ค๋ณด๋ฉด nxt[a][b]์๋ "a ๋ฐฉ๋ฌธ ํ, ๋ฐ๋ก ๋ค์์ผ๋ก ๋ฐฉ๋ฌธํด์ผ ํ ๋
ธ๋"๊ฐ ์ ์ฅ๋ ๊ฒ์ด๋ค.
๐์ดํด๊ฐ ์ ์๋ ๊ฒฝ์ฐ ์๋์ ์ง๋ฌธ๊ธ์ ์ฐธ๊ณ ํด๋ณด๋ฉด ์ข์๊ฒ๊ฐ๋ค.
https://www.acmicpc.net/board/view/104174
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 33432KB / ์๊ฐ: 584ms
from sys import stdin
input = stdin.readline
INF = int(1e9)
def main():
N, M = map(int, input().split())
graph = [[INF] * N for _ in range(N)]
nxt = [[-1] * N for _ in range(N)]
for _ in range(M):
u, v, w = map(int, input().split())
graph[u-1][v-1] = w
graph[v-1][u-1] = w
nxt[u-1][v-1] = v
nxt[v-1][u-1] = u
for k in range(N):
for i in range(N):
for j in range(N):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
nxt[i][j] = nxt[i][k]
for i in range(N):
line = ["-" if i == j else nxt[i][j] for j in range(N)]
print(*line)
main()