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

- ๋ชจ๋ A-B(B-A)๋ ์ฐ๊ฒฐ๋์ด์๋ค.(์ง์ or ์ฐํ)
- ์ฃผ์ด์ง ๊ฐ์ ๋ค์ ๋ชจ๋ ์ต๋จ๊ฒฝ๋ก ๊ฐ์ด๋ค.
- ๋จ, ๊ฐฏ์๋ "์ต์"๊ฐ ์๋๋ค.
์ผ๋จ ์ฃผ์ด์ง ๊ฐ๋ค๋ก A-B ์์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ์๋ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๋ง์กฑํ๋์ง ํ์ธํด์ผํ๋ค. ์ต์ ๊ฐฏ์๋ฅผ ๋ง์กฑํ๋์ง๋ ๋ค์ ๋ฌธ์ ๋ค.
A-B ์งํ๋ณด๋ค A-K + K-B ์ฐํ๊ฐ์ด ๋ ํฌ๋ค๋ฉด ์ต๋จ๊ฒฝ๋ก๊ฐ ์๋ ์
. (๊ฐ์ ๊ฒฝ์ฐ๋ ๊ด์ฐฎ๋ค)
์ฒซ๋ฒ์งธ ์กฐ๊ฑด์ ๋ง์กฑํ์ง ๋ชปํ๋ค๋ฉด ๋ฐ๋ก -1๋ฅผ ์ถ๋ ฅํด์ฃผ๊ณ , ๋ง์กฑํ๋ค๋ฉด ๋ค์ ๋จ๊ณ๋ก ๋์ด๊ฐ๋ค.
์์ ์ ํจ๊ป ๋ณด๋ฉด ์ดํด๊ฐ ์ฝ๋ค.

๊ผญ ํ์ํ ๋๋ก๋ง ๋จ๊ฒจ๋๊ณ ๋๋จธ์ง๋ ์ ๊ฑฐํ๋ค. ๋จ๊ฒจ๋ ๋๋ก๋ค์ ํฉ์ด ๋ฌธ์ ์์ ๋งํ๋ "๋ชจ๋ ๋๋ก์ ์๊ฐ์ ํฉ"์ด ๋๋๊ฒ์ด๋ค.
๋ง์ฝ A-B(์งํ๊ฐ) == A-K + K-B(์ฐํ๊ฐ)์ด๋ผ๋ฉด A-B ๋๋ก๋ ๊ตณ์ด ํ์ํ์ง ์๋ค. ๊ฐ์ ๋น์ฉ์ผ๋ก ์ฐํํด์ ๊ฐ ์ ์๊ธฐ ๋๋ฌธ.
๋ฐ๋ผ์ ์งํ๊ฐ์ด ์ฐํ๊ฐ๋ณด๋ค ์ ์ ๊ฒฝ์ฐ์๋ง ๊ฒฐ๊ณผ๊ฐ์ ์ถ๊ฐํ๋ค.
์ ์ฒด์ ์ธ ๊ณผ์ ์ ๋ค์๊ณผ ๊ฐ๋ค.
- ํ๋ก์ด๋ ์์
์ ์ํํ๋ฉฐ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๋ง์กฑํ๋์ง ํ์ธ.
- ๊ฐฑ์ ์ X
- A-K + K-B ๊ฐ์ด ๋ ํจ์จ์ ์ด๋ผ๋ฉด? ์ฃผ์ด์ง ๊ฐ๋ค์ด ์ต๋จ๊ฒฝ๋ก๊ฐ ์๋๊ฒ์ด๋ฏ๋ก -1๋ฅผ ๋ฐํํ๋ค.
- ๋ค์ ํ ๋ฒ ํ๋ก์ด๋ ์์
์ ์ํํ๋ฉฐ ์ต์ํ์ ๋๋ก๋ง ๋จ๊ฒจ๋๋ค.
- A-B ์งํ๊ฐ์ด A์์ B๋ก ๊ฐ๋ ์ต๋จ๊ฒฝ๋ก์ผ๋์๋ง ๋จ๊ฒจ๋ .
- ์ ์ฒด ๊ฒฐ๊ณผ๊ฐ์ A-B ๋๋ก ๋น์ฉ์ ์ถ๊ฐ.
- ์๋๋ผ๋ฉด ๊ทธ๋ฅ ๋์ด๊ฐ๋ค.
ํ๋ก์ด๋ ์์ ์ "ํ์ฉ"ํ๋ ๋ฌธ์ ๋ผ๊ณ ํ ์ ์๊ฒ ๋ค.
์ ์ฒด ์ฝ๋
"""
1. ์ต๋จ ๊ฒฝ๋ก ๊ทธ๋ํ์ธ์ง ํ์ธ
2. ์๋๋ผ๋ฉด -1, ๋ง๋ค๋ฉด ๋ค์ ๋จ๊ณ๋ก
3. ํ๋ก์ด๋ ์์
์ํ -> ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์
๋ฐ์ดํธ๋ X
4. A - C ๋๋ก๋ฅผ ๊ฒ์ฌํ ๋, A - B - C ๊ฐ๊ณผ A - C ๊ฐ์ด ๊ฐ๋ค๋ฉด ํ์ํ ๋๋ก๊ฐ ์๋์ธ ์
์ด๋ฏ๋ก ๋์ด๊ฐ.
5. ๋ชจ๋ B๋ฅผ ๊ฑฐ์น ํ ํ์ํ ๋๋ก๋ก ํ์ ๋๋ฉด ๊ฒฐ๊ณผ๊ฐ์ ์ถ๊ฐ
"""
# ๋ฉ๋ชจ๋ฆฌ: 32412KB / ์๊ฐ: 40ms
from sys import stdin
input = stdin.readline
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
# ์ต๋จ ๊ฒฝ๋ก ๊ทธ๋ํ๊ฐ ์๋๋ผ๋ฉด -1 ๋ฐํ
def checking():
for k in range(N):
for i in range(N):
for j in range(N):
# ์ฐํํ๋ ๋ฐฉ๋ฒ์ด ๋ ํจ์จ์ ์ด๋ผ๋ฉด ์ต๋จ ๊ฒฝ๋ก ๊ทธ๋ํ๊ฐ ์๋์
if graph[i][k] + graph[k][j] < graph[i][j]:
return False
return True
if not checking():
print(-1)
exit()
time = 0
for i in range(N):
for j in range(i+1, N):
flag = True
for k in range(N):
# ๊ฒฝ์ ์ง๊ฐ ์ถ๋ฐ์ง or ๋์ฐฉ์ง๊ฐ ์๋๊ณ , ์ฐํํด์ ๋์ฐฉํ๋ ๊ฐ๊ณผ ์ผ์ง์ ๋๋ก์ ๊ฐ์ด ๊ฐ๋ค๋ฉด
# => ์ผ์ง์ ๋๋ก๋ ๊ตณ์ด ์กด์ฌํ ํ์๊ฐ ์์
if k != i and k != j and graph[i][k] + graph[k][j] == graph[i][j]:
flag = False
break
if flag:
time += graph[i][j]
print(time)
์ฌ์ค ์ต์์ ์ฅํธ๋ฆฌ(MST)๊ฐ์ ๊ตฌํ๋ฉด ๋์ง ์๋? ์ถ์ด์ ๋์ ํด๋ดค๋๋ฐ ์คํจํ๋ค.
์กฐ๊ธ ๋ ์๊ฐํด๋ณด๋ ๋น์ฐํ ๋ฌธ์ ์์.
๋ง์ฝ ๋
ธ๋ A, B, C, D์ ๊ฐ์ ์ด ์๋์ ๊ฐ์ด ๊ตฌ์ฑ๋์ด์๋ค๊ณ ๊ฐ์ ํด๋ณด์.
A-B = 1
A-D = 2
B-C = 1
C-D = 1
MST๋ฅผ ๊ตฌํ๊ฒ ๋๋ฉด (A-B, B-C, C-D) ์์ผ๋ก ์ด์ด์ง๊ฒ ๋ค. ์ด ๊ฒฝ์ฐ A-D์ ๊ฐ์ 3์ด ๋๋ค.
ํ์ง๋ง ์ค์ ๋ก A-D์ ์ต๋จ๊ฒฝ๋ก๋ 2์ด๋ค. ํ!
๊ฒฐ๋ก ์ ์ผ๋ก ์ฝ์ง์ ์๊ฐ์ด์์ง๋ง, ๋ง์ฐํ๊ฒ '์ด๋ฐ ๋ฌธ์ ๋ ๋ฌด์กฐ๊ฑด ํ๋ก์ด๋ ์์
์ด์ผ~'ํ๋๊ฒ๋ณด๋จ ๋ซ๋ค.