๋ฌธ์
https://www.acmicpc.net/problem/11780
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x1C๊ฐ - ํ๋ก์ด๋ ์๊ณ ๋ฆฌ์ฆ
์๊ณ ๋ฆฌ์ฆ: ํ๋ก์ด๋-์์ , ์ญ์ถ์
ํ์ด

ํ๋ก์ด๋ ์์
์ ํตํด ์ต๋จ๊ฒฝ๋ก(์ต์๋น์ฉ)๋ฅผ ๊ตฌํ๊ณ , ๊ฒฝ๋ก๋ฅผ ์ถ๋ ฅํด์ผํ๋ ๋ฌธ์ ๋ค.
๐จ์ฃผ์ํด์ผ ํ ์ ์ "์์๋์์ ๋์ฐฉ๋์๊ฐ ๊ฐ์ ๊ฒฝ์ฐ๋ ์๋ค." ๋ถ๋ถ์ธ๋ฐ, ์ค๋ณต๊ฒฝ๋ก๊ฐ ์๋ค๋ ๊ฒ ์๋๋ผ "์์๋์ != ๋์ฐฉ๋์"๋ผ๋ ๋ป์ด๋ค.
๋ฐ๋ผ์ ๊ฐ์ ์ ๋ณด๋ฅผ ์
๋ ฅ๋ฐ์ ์ ๊ธฐ์กด ๋น์ฉ๊ณผ ๋น๊ตํ ๋ค ๊ฐฑ์ ํด์ผํ๋ค.
์ฌ์ค ์ด ๋ฌธ์ ์ ์ฃผ์ ํฌ์ธํธ๋ ์ญ์ถ์ ์ด๋ค.
ํ๋ก์ด๋ ์์
์ ์ํ ํ, a - b์ ์ต๋จ๊ฒฝ๋ก๋ a - c - d - b ์ฒ๋ผ ๊ตฌ์ฑ๋ ๊ฐ๋ฅ์ฑ์ด ๋๋ค.
๊ทธ๋ฌ๋ฏ๋ก ์ต๋จ๊ฒฝ๋ก ๊ฐฑ์ ์, a - b์ ๊ฒฝ๋ก๋ ๊ฐฑ์ ํด์ฃผ์ด์ผ ํ๋ค.
a - b์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ๊ณผ์ ์ ์์๋ก ๋ณด์.
๋ง์ฝ k = c์ผ๋ a - c - b๊ฐ ๊ธฐ์กด ๊ฒฝ๋ก๋ณด๋ค ๊ฐ์ด ์๋ค๋ฉด a - b์ ๊ฒฝ๋ก ๋ฆฌ์คํธ๋ [a, c, b]๊ฐ ๋์ด์ผ ํ๋ค.
ํ์ง๋ง ๋ชจ๋ ๊ฒฝ๋ก๋ฅผ ๋ฆฌ์คํธ๋ก ๊ด๋ฆฌํ๊ธด ๋ถ๋ด์ค๋ฌ์ฐ๋, ๋์ nxt[i][j] ๋ฐฐ์ด์ ์ด์ฉํด "i์์ j๋ก ๊ฐ๋ ๊ฒฝ๋ก ์ค, i ๋ค์์ ๊ฐ์ผ ํ ๋์"๋ง ์ ์ฅํด๋๋ ๋ฐฉ์์ผ๋ก ๊ฒฝ๋ก๋ฅผ ์์ถํ์ฌ ๊ด๋ฆฌํ๋ค.
๊ธฐ๋ณธ์ ์ธ ์ ํ ์ ๊ฐ์ ์ ๋ณด ์ ์ฅ๊ณผ ํจ๊ป ์งํํ๋ค.
๋์ผ ๊ฒฝ๋ก๊ฐ ์ฌ๋ฌ๋ฒ ์ฃผ์ด์ง ์ ์์ผ๋ฏ๋ก, ๊ธฐ์กด์ ์ ์ฅ๋ ๋น์ฉ์ด ์๋ค๋ฉด ๋น๊ตํด๋ด์ผ ํ๋ค.
a - b์ ๊ธฐ์กด ๋น์ฉ๋ณด๋ค ์๋ก์ด ๋น์ฉ c๊ฐ ๋ ์์ ๊ฒฝ์ฐ graph[a][b] = c๋ก ์ ์ฅ/๊ฐฑ์ ์์ผ์ค๋ค.
(nxt๋ ์ง๊ธ์ ์๊ด X. ๋น์ฉ์ด ์ด๋ป๋ a ๋ค์์ ๋ฌด์กฐ๊ฑด b๋ฅผ ๊ฐ์ผ ํ๋ฏ๋ก b ์ ์ฅ.)
๋ณธ๊ฒฉ์ ์ธ ๊ฒฝ๋ก ๊ฐฑ์ ์ ํ๋ก์ด๋ ์์
๊ณผ ํจ๊ป ์งํ๋๋๋ฐ, k๋ฅผ ๊ฑฐ์ณ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ๋ ํจ์จ์ ์ด๋ผ๋ฉด nxt[a][b]์ nxt[a][k]์ ๊ฐ์ ์ ์ฅํ๋ ๋ฐฉ์์ด๋ค.
์ฆ "a์์ k๋ก ๊ฐ๋ ๊ฒฝ๋ก ์ค, a ๋ค์์ ๊ฐ์ผ ํ ๋์"๋ฅผ ๋งตํ์์ผ์ฃผ๋ ๊ฒ์ด๋ค.
์๋ฅผ๋ค์ด a - b์ ์ต๋จ๊ฒฝ๋ก ๊ตฌ์ฑ์ด a - c - d - e - b ๋ผ๋ฉด nxt๋ฐฐ์ด์ ๋ค์๊ณผ ๊ฐ์ด ๊ตฌ์ฑ๋๋ค.
[a]๋ก ์ด๊ธฐํ ํ ์ญ์ถ์ ์์
nxt[a][b] = c
ํ์ฌ๊น์ง์ ๊ฒฝ๋ก = [a, c]
nxt[c][b] = d
ํ์ฌ๊น์ง์ ๊ฒฝ๋ก = [a, c, d]
nxt[d][b] = e
ํ์ฌ๊น์ง์ ๊ฒฝ๋ก = [a, c, d, e]
nxt[e][b] = b
ํ์ฌ๊น์ง์ ๊ฒฝ๋ก = [a, c, d, e, b]
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 33432KB / ์๊ฐ: 212KB
from sys import stdin
input = stdin.readline
INF = int(1e9)
def main():
n = int(input())
m = int(input())
graph = [[INF] * (n+1) for _ in range(n+1)]
nxt = [[-1] * (n+1) for _ in range(n+1)] # nxt[a][b] = a์์ b๋ก ๊ฐ๊ธฐ ์ํด ๋ฐฉ๋ฌธํด์ผํ ์ฒซ๋ฒ์งธ ๋
ธ๋
# 1. ๊ฐ์ ์ ๋ณด ์ ์ฅ
for i in range(1, n+1):
graph[i][i] = 0
for _ in range(m):
a, b, c = map(int, input().split())
# ์๋ก์ด ๋น์ฉ c๊ฐ ๊ธฐ์กด ๋น์ฉ๋ณด๋ค ์์๋์๋ง graph, nxt ๊ฐฑ์
if c < graph[a][b]:
graph[a][b] = c
nxt[a][b] = b # nxt๋ ๊ธฐ์กด ๋น์ฉ๋ณด๋ค ์์๋์๋ง ๊ฐฑ์ !
# 2. ํ๋ก์ด๋-์์
์ํ
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
cost = graph[i][k] + graph[k][j]
# k๋ฅผ ๊ฑฐ์น๋ ๋น์ฉ์ด ๊ธฐ์กด ๋น์ฉ๋ณด๋ค ์๋ค๋ฉด ๊ฐฑ์
if cost < graph[i][j]:
graph[i][j] = cost
nxt[i][j] = nxt[i][k] # i-k์ ๊ฒฝ๋ก ๊ฐ์ i-j์ ์ ์ฅ
def get_path(s: int, e: int) -> list:
"""
๊ฒฝ๋ก ์ญ์ถ์ ํจ์
- [a, [b, [c, [d, [e]]]]] ์ด๋ฐ์์ผ๋ก, ๊ฐ์ฅ ๋ฐ๊นฅ๊ดํธ๋ถํฐ ์์ชฝ ๊ดํธ๊น์ง ํ๊ณ ๋ ๋ค๊ณ ์๊ฐํ๋ฉด ๋จ.
- s๊ฐ a -> b -> c -> d -> e๋ก ๋ณํํ๊ฒ ๋๋๊ฒ!
- ์งํ ๊ณผ์ ์์
- ์ด๊ธฐ path = [a]
- a์์ e๋ก ๊ฐ๊ธฐ ์ํด ๊ฐ์ฅ ์ฒซ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํด์ผ ํ ๋
ธ๋ = b, path = [a, b]
- b์์ e๋ก ๊ฐ๊ธฐ ์ํด ๊ฐ์ฅ ์ฒซ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํด์ผ ํ ๋
ธ๋ = c, path = [a, b, c]
- c์์ e๋ก ๊ฐ๊ธฐ ์ํด ๊ฐ์ฅ ์ฒซ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํด์ผ ํ ๋
ธ๋ = d, path = [a, b, c, d]
- d์์ e๋ก ๊ฐ๊ธฐ ์ํด ๊ฐ์ฅ ์ฒซ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํด์ผ ํ ๋
ธ๋ = e, path = [a, b, c, d, e]
"""
path = [s]
while s != e:
s = nxt[s][e]
path.append(s)
return path
# 3. ์ต์๋น์ฉ ์ถ๋ ฅ
for i in range(1, n+1):
print(" ".join(map(lambda x: str(x) if x != INF else "0", graph[i][1:])))
# 4. ๊ฒฝ๋ก ์ถ์ ํ ์ถ๋ ฅ
for i in range(1, n+1):
for j in range(1, n+1):
# ์์์ == ๋์ ์ด๊ฑฐ๋, i-j๋ก ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ์๋ค๋ฉด 0 ์ถ๋ ฅ
if i == j or graph[i][j] == INF:
print(0)
else:
path = get_path(i, j)
print(len(path), *path)
main()
๋ธ๋ก๊ทธ๋ฅผ ์ํด ๋ค์ ํ์ด๋ดค๋๋ฐ... ๊ธฐ์กด ํ์ด๋ ์ ๋ ฅ๋ฐ์ดํฐ ์ ์ฅ ์ ์๋์ ๊ฐ์ด ์งํ๋์๋ค.
for a, b, c in route:
if c < dp[a-1][b-1]: # ๊ธฐ์กด ๊ฒฝ๋ก๊ฐ๋ณด๋ค ์์ผ๋ฉด ์
๋ฐ์ดํธ.
dp[a-1][b-1] = c
nxt[a-1][b-1] = b-1
(dp = graph)
๋ณด๋ฉด c๊ฐ ๊ธฐ์กด ๊ฐ๋ณด๋ค ํด๋/์์๋ ์๊ด ์์ด ๋ฌด์กฐ๊ฑด nxt๋ฅผ ๊ฐฑ์ ์ํจ๋ค.
์๋ฌด ์๊ฐ ์์ด ์ด ๋ถ๋ถ์ด ์๋ชป๋๋ค๊ณ ์๊ฐํ๊ณ , ๋ค์ ํ ๋ ์์ ํ๋๋ฐ ์ง์ง ๋ฐ๋ณด์๋ค;;;
1 3 4, 1 3 1์ด ์ฃผ์ด์ง๋ค๋ฉด ๋น์ฉ๊ณผ ๊ด๊ณ์์ด nxt[1][3] = 3 ์ด๋ค.
๋ค๋ฅธ ๊ณณ์ ๊ฑฐ์ณ๊ฐ๋๊ฒ ์ต๋จ๊ฒฝ๋ก๋ผ๋ฉด ํ๋ก์ด๋ ์์ ์ํ ์ค ์์์ ๊ฐฑ์ ๋ ๊ฒ์ด๊ณ .
๋ญ ์์ ํด๋ ๊ฒฐ๊ณผ๊ฐ์ ์ฐจ์ด๋ ์์ด์ ๋ฌธ์ ๋ ๊ฑด ์์ง๋ง... ์๊ฐ์ ์ค๋ฅ๊ฐ ์์๋๊ฑฐ๋...
์ด์จ๋ ... ๋ค๋ฆ๊ฒ๋๋ง ์ด ๋ฐ๋ณด์ง์ ๋ฐ๊ฒฌํด์ ๋คํ.