TIL - 프로그래밍/Python 알고리즘
[백준] 11404. 플로이드 - Python
chaemj97
2022. 6. 15. 22:37
728x90
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
- 생각
- 모든 점 -> 모든점 : 플로이드
- 거리 초기값 무한대, 자기 자신으로 가는 값 0
- 노드 거쳐거 가서 비용 작아질 경우 값 갱신
- 코드
import sys
# 도시의 개수
n = int(input())
# 버스의 개수
m = int(input())
INF = sys.maxsize
money = [[INF]*n for _ in range(n)]
for _ in range(m):
# [버스 시작 도시, 버스 도착 도시, 한번 타는데 필요한 비용]
a,b,c = map(int,input().split())
# 버스번호는 1번부터, index는 0번부터
# 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
money[a-1][b-1] = min(money[a-1][b-1],c)
# 자기 자신으로 가는 경우
for i in range(n):
money[i][i] = 0
# k : 거치는 곳, i : 시작, j : 도착
for k in range(n):
for i in range(n):
for j in range(n):
# 시작에서 도착으로 가는게 k를 거쳐가는 것보다 크면
if money[i][j] > money[i][k] + money[k][j]:
money[i][j] = money[i][k] + money[k][j]
# 출력
for i in range(n):
for j in range(n):
# i에서 j로 갈 수 없다면
if money[i][j] == INF:
print(0,end=' ')
else:
print(money[i][j],end=' ')
print()
728x90
반응형