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

๋ ๋ง์์ ์๋ณตํ๋ ๊ฒฝ์ฐ๋ ์ฌ์ดํด์ ํฌํจ๋๋ค.
์ฆ, ํ๋ก์ด๋ ์์
๋ก ๊ฐ ๋ง์ ์ฌ์ด์ ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ์ ๊ตฌํ ๋ค์ ํ ๋ง์์ ๊ธฐ์ ์ผ๋ก ๋ค๋ฅธ ๋ง์๊น์ง์ ์๋ณต๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐํ๋ฉด ๋๋ค.
์์๋ง์ A, ๋์ฐฉ๋ง์ B์ผ๋ A → B์ ๊ฐ + B → A์ ๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฒฝ์ฐ๋ฅผ ์ ํํ๋ฉด ๋๋ ๊ฒ์ด๋ค. (์ผ๋ฐฉํตํ์ด๋ฏ๋ก A-B, B-A์ ๊ฐ์ด ๋ค๋ฅด๋ค.)
์ฌ์ค ๋ฌธ์ ์์ฒด๋ ์ด๋ ต์ง ์๋ค. ๋จ์ํ ํ๋ก์ด๋ ์์
๋ฌธ์ ์ ๊ฐ๊น๋ค.
ํ์ง๋ง ์กฐ๊ฑด์์ ์ด๋ป๊ฒ ์์ฑํ๋์ง์ ๋ฐ๋ผ ์๊ฐ์ด๊ณผ๊ฐ ๋ ์๋ ์์ผ๋ ์ฃผ์ํด์ผํ๋ค.
์ ์ฒด์ ์ธ ๊ณผ์ ์ ์๋์ ๊ฐ๋ค.
- ๊ฐ ๋ง์ ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ทธ๋ํ์ ์ ์ฅ. (a, b)์์ด ๊ฐ์ ๋๋ก๊ฐ ์ฌ๋ฌ๋ฒ ์ฃผ์ด์ง์ง ์์.
- ํ๋ก์ด๋ ์์ ์ํ
- ์์ ๋ง์ A๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ค๋ฅธ ๋ง์ B๊น์ง์ ์๋ณต ๊ฑฐ๋ฆฌ๋ค์ ๊ณ์ฐ.
- ๊ฐ์ฅ ์งง์ ๊ฑฐ๋ฆฌ๊ฐ ๊ฒฐ๊ณผ๊ฐ.
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 37660KB / ์๊ฐ: 5832ms
from sys import stdin
input = stdin.readline
INF = float("inf")
def main():
V, E = map(int, input().split())
graph = [[INF] * V for _ in range(V)]
for _ in range(E):
a, b, c = map(int, input().split())
graph[a-1][b-1] = c
for k in range(V):
for i in range(V):
for j in range(V):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
min_dis = INF
for i in range(V):
for j in range(i+1, V):
if min_dis > graph[i][j] + graph[j][i]:
min_dis = graph[i][j] + graph[j][i]
print(min_dis if min_dis != INF else -1)
main()
์ฐธ๊ณ ๋ก ์๋ ์ฝ๋๋ ์๊ฐ์ด๊ณผ๋ค.
from sys import stdin
input = stdin.readline
INF = float("inf")
def main():
V, E = map(int, input().split())
graph = [[INF] * (V+1) for _ in range(V+1)]
for _ in range(E):
a, b, c = map(int, input().split())
graph[a][b] = c
for k in range(1, V+1):
for i in range(1, V+1):
for j in range(1, V+1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
min_dis = INF
for i in range(1, V+1):
for j in range(1, V+1):
min_dis = min(min_dis, graph[i][j] + graph[j][i])
print(min_dis if min_dis != INF else -1)
main()
โญ์ฃผ์ ์ฐจ์ด์ ์ ์๋์ ๊ฐ๋ค.
min()๋์<, >๋น๊ต์ฐ์ฐ์ ์ฌ์ฉ- ๋ ๋ค ๋ง์ ์ฐ์ฐ ํ ๋น๊ตํ๋๊ฑด ๋๊ฐ์.
- ํ์ง๋ง
min()์ ๊ฒฝ์ฐ ์ฐธ/๊ฑฐ์ง๊ณผ ์๊ด์์ด ๋ฌด์กฐ๊ฑด "๋์ "์ ํ๊ฒ ๋จ.
- ๋ฆฌ์คํธ ํฌ๊ธฐ ์ค์
- ๋ง์ ๋ฒํธ๋ 1๋ถํฐ ์์๋๋ฏ๋ก ๊ทธ๋ํ ์ ์ฅ ์ -1์ฒ๋ฆฌ๋ฅผ ํด์ฃผ๊ฑฐ๋ ๋ฆฌ์คํธ ํฌ๊ธฐ๋ฅผ
(V+1)๋ก ์ค์ ํด์ผํจ. (๋ค๋ง ์ด ๋ฌธ์ ์์์ ๊ฒฐ์ ์ ํฌ์ธํธ๋ ์๋๋ค.)
- ๋ง์ ๋ฒํธ๋ 1๋ถํฐ ์์๋๋ฏ๋ก ๊ทธ๋ํ ์ ์ฅ ์ -1์ฒ๋ฆฌ๋ฅผ ํด์ฃผ๊ฑฐ๋ ๋ฆฌ์คํธ ํฌ๊ธฐ๋ฅผ
- ๋ง์ง๋ง for๋ฌธ์ ๋ฒ์ ์ค์
- ๐จ์ด๊ฒ ์ ์ผ ์ค์ํ๋ค๊ณ ์๊ฐํ๋ค.
- ๋ฌธ์ ์์ ์ํ๋ ๊ฐ์ "๊ฑฐ๋ฆฌ"๊ฐ์ด์ง "์ด๋ค ๋ง์"์ธ์ง๊ฐ ์ค์ํ๊ฒ ์๋๋ค.
- (AB, BA)๊ฐ์ ์์๋ง์์ B๋ก ์ค์ ํ์๋์ ๊ฐ(BA, AB)์๋ ๊ฐ์ผ๋ฏ๋ก, ์์ด์ด ์๋ ์กฐํฉ์ผ๋ก ํ๋จํด๋ ๋๋ค.
์ฌ์ค 1๋ฒ์ด ์ฃผ์ ํฌ์ธํธ๋ผ๊ณ ์๊ฐํ๋๋ฐ, ๋ญ๊ฐ ์ด์ํด์ ๋ค์ ๋๋ ค๋ณด๋ 3๋ฒ์ด์๋ค.
์ค์๋ ์์๋ 3 > 1 >> 2 ์ธ๋ฏ ์ถ๋ค...
๋ฆฌ์คํธ ํฌ๊ธฐ๋ง V๋ก ๋ณ๊ฒฝํ์๋๋ ๋๊ฐ์ด ์๊ฐ์ด๊ณผ์๊ณ , for๋ฌธ ๋ฒ์ ๋ณ๊ฒฝ or ๋น๊ต์ฐ์ฐ์ ์ฌ์ฉ ์ค ํ๋๋ง ์ ์ฉํด๋ ํต๊ณผ๋๋ค.