[백준(BOJ)] 1956번 : 운동 - PYTHON[파이썬]

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

1956번: 운동

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 플로이드-와샬

 

---

 

⊙ 문제 접근 과정

 

플로이드 와샬을 통해 다시 돌아온 arr[i][i] 값 중 가장 작은 값을 출력해주면 된다.

만약 갱신이 안 되었을 시 -1을 출력해주면 된다.

 

자세한 설명은 코드에 주석으로 적어놨다!

---

 

⊙ 문제 풀이

 

import sys

V, E = map(int, sys.stdin.readline().split())
INF = 999999
arr = [[INF] * V for i in range(V)] #길 없음을 표시
for i in range(E):
    x, y, z = map(int, sys.stdin.readline().split())
    arr[x-1][y-1] = z #길 있음을 표시
#플로이드 와샬
for k in range(V): # k = 거쳐가는 노드
    for i in range(V): # i = 출발 노드
        for j in range(V): # j = 도착 노드
            if arr[i][j] > arr[i][k] + arr[k][j]: #더 작은 값
                arr[i][j] = arr[i][k] + arr[k][j]
result = INF #초기화
for i in range(V): #다시 시작점으로 돌아온 값 중 가장 작은 값 갱신
    result = min(result,arr[i][i])
if result == INF: print(-1) #결과 출력
else: print(result)

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!