[Python] 백준 1956번 : 운동

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

1956번: 운동

---

💡 문제 풀이

플로이드-워샬 문제이다.

 

각 노드 사이의 최단거리를 구하고 만들어지는 사이클에 대한 최솟값을 구하면 된다

사이클은 단순히 시작점에서 목표 지점과 목표 지점에서 시작점을 접근할 수 있는지만 확인하면 된다..

일방통행이라 다양한 경우를 따지지 않아도 괜찮다.

✔️ 느낀 점

중간에 사이클을 어떻게 고려할까 고민을 조금했는데 생각해 보면 간단한 문제였다.

💻 코드

import sys
input = sys.stdin.readline

INF = int(1e9)

def initBoard():
    board = [[INF] * (v+1) for _ in range(v+1)]
    
    for i in range(1, v+1):
        board[i][i] = 0
    
    for _ in range(e):
        start, end, cost = map(int, input().split())
        board[start][end] = cost
    
    return board

def floydWarshall(board):
    for k in range(1, v+1):
        for i in range(1, v+1):
            for j in range(1, v+1):
                board[i][j] = min(board[i][j], board[i][k] + board[k][j])
                
def findCourse(start, board):
    sumCourse = INF
    
    for i in range(v+1):
        if start == i: continue
        sumCourse = min(sumCourse, board[start][i] + board[i][start])
        
    return sumCourse

v, e = map(int, input().split())
board = initBoard()
floydWarshall(board)

course = INF
for i in range(1, v+1):
    course = min(course, findCourse(i, board))
    
print(course if course != INF else -1)