백준 11404 파이썬
문제
플로이드
풀이
플로이드 와샬 문제의 기본이다.
알고리즘 설명은 패스한다.
기본만 기억하자
플로이드 와샬의 기본 핵심은 모든 정점의 최단거리를 구하는 것 이다.
그렇기 때문에 모든 정점에서 모든 정점의 최단 거리를 구하는 문제가 나오면 이 알고리즘을 사용하면 된다.
기본 알고리즘 또한 정말 정말 정말 간단하다.
python을 기준으로 for 문 3중첩만 하면 된다.
어때요.. 정말 쉽죠?for i in range(n): for j in range(n): for k in range(n): arr[j][k]=min(arr[j][k],arr[j][i]+arr[i][k])
# 플로이드 기본문제
import sys
input=sys.stdin.readline
n=int(input())
m=int(input())
# n개의 도시의 경로를 전부 무한대 으로 초기화
city=[[10000000 for _ in range(n)] for _ in range(n)]
for i in range(m):
c1,c2,value=map(int,input().split())
city[c1-1][c2-1]=min(city[c1-1][c2-1],value)
for i in range(n):
city[i][i]=0
for i in range(n):
for j in range(n):
for k in range(n):
city[j][k]=min(city[j][k],city[j][i]+city[i][k])
for i in city:
for j in i:
if j==10000000:
j=0
print(j,end=' ')
print()
첫 번째 시간초과
import sys
input=sys.stdin.readline
이 부분을 안하면 가끔 python에서는 시간초과가 난다.. 항상 추가 해 줄 것
결과 정답
Author And Source
이 문제에 관하여(백준 11404 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chuneeeee/백준-11404-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)