Algorithm/백준
[플로이드워셜] 11404번 - 플로이드 - python, 골드4
sdoaolo
2023. 1. 25. 01:49
728x90
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
플로이드 개념 공부+코드이해를 하자마자 대놓고 똑같은 문제여서 그냥 복습이 바로 된 느낌이다.
특수한 개념은 없지만 고려해야할점은
0. 도시 == 노드, 버스 == 간선이라는 것을 알고
1. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. >> 이걸 잘 처리해주면 되는 문제!
(예제 입력을 보면 1에서 4로가는 간선이 여러개가 있었다)
2. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다. >> 마지막에 INF이면 0출력
💻 내가 쓴 정답 CODE
#플로이드 백준 11404 골드4
import sys
input = sys.stdin.readline
INF = sys.maxsize
n = int(input()) #도시의 개수 (노드)
m = int(input()) #버스의 개수 (간선)
dist = [[INF]*n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for _ in range(m) :
start, end, cost = map(int,input().split())
if dist[start-1][end-1] > cost:
dist[start-1][end-1] = cost
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
#출력
for i in range(n):
for k in range(n):
if(dist[i][k] == INF):
print(0,end=' ')
else:
print(dist[i][k], end=' ')
print()
내일 플로이드 관련문제 하나 더 풀어보고
다익스트라 공부도 해야겠다.
내일 참고할 블로그!
https://it-garden.tistory.com/241