1956

날짜 : 2023. 06. 20

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/1956

 

 

코드

import sys
import copy

v, e = map(int, sys.stdin.readline().split())  # 마을, 도로
graph = [[10**9] * (v) for _ in range(v)]
for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a-1][b-1] = c

fir = copy.deepcopy(graph) # 계산용

# 플로이드 워셜
for j in range(v):
    for i in range(v):
        for k in range(v):
            if i == k: continue
            fir[i][k] = min(fir[i][k], fir[i][j] + fir[j][k])
res = 10**9 # 결과값

# 사이클(a - > b 와 b -> a의 합) + 최소값 구하기
for i in range(v):
    for j in range(v):
        if i == j: continue
        res = min(fir[i][j] + fir[j][i], res)

# for i in fir:
#     print(i)

if res == 10**9: print(-1)  # 해당하는 값이 없는 경우
else: print(res)

 

 

풀이

- 조건에 맞게 데이터를 입력받은 후 플로이드 워셜을 사용해 a -> b로 구하는 최단경로를 구하고, 사이클 조건에에 맞추어 결과값을 구한다.

- 노드의 최대 개수가 400이기 때문에 400^3 = 64,000,000 < 100,000,000 이기 때문에 TLE는 발생하지 않는다.

=> 플로이드 워셜 사용 가능

- 사이클은 a 노드에서 b 노드에 갔다가, b 노드에서 a 노드로 가는 것을 의미하기 때문에, 플로이드 워셜을 통해 각 노드로 가는 cost를 구한 그래프에서 갱신하는 방향으로 진행하면 된다.

- 다만 값이 없는 경우(res = 10**9)가 있을 수 있기 때문에 마지막에 조건문을 달아준다.

 

 

알게된 점

- 사이클에서 조금 고민했던 것 같다.

- 플로이드 워셜을 사용하면서 최대, 최소값 처리도 고민한듯

 

 

참고 사이트

-