문제풀이/BOJ
[Python] BOJ/백준 1956번 운동
서채리
2022. 8. 26. 00:11
[문제]
https://www.acmicpc.net/problem/1956
1956번: 운동
첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의
www.acmicpc.net
[풀이]
2022.08.23 - [문제풀이/BOJ] - [Python] BOJ/백준 11404번 플로이드
[Python] BOJ/백준 11404번 플로이드
[문제] https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어
chaewsscode.tistory.com
위 문제랑 엄청 엄청 유사한 문제!!
[코드]
import sys
INF = int(1e9)
V, E = map(int, sys.stdin.readline().split())
my_map = [[INF] * V for _ in range(V)]
for _ in range(E):
a, b, c = map(int, sys.stdin.readline().split())
my_map[a-1][b-1] = c
for k in range(V):
for i in range(V):
for j in range(V):
if my_map[i][j] > my_map[i][k] + my_map[k][j]:
my_map[i][j] = my_map[i][k] + my_map[k][j]
answer = INF
for i in range(V):
for j in range(V):
answer = min(answer, my_map[i][j] + my_map[j][i])
if answer == INF:
print('-1')
else:
print(answer)