https://www.acmicpc.net/problem/11404
11404번: 플로이드첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가www.acmicpc.net
내 기억상 유튜브에서 보고 처음으로 감탄사를 내뱉었던 알고리즘
우리는 n*n 배열을 만들거다.
배열 i,j는 i에서 j로가는 최소 경로이다.
직접가는 버스가 있으면 가중치를, 없으면 존나큰값을 넣는다.
n에 대한 3중 반복문을 돌면서,
arr[i][j]가arr[i][k]+arr[k][j] 즉 직접가는 경로보다 k지점을 거쳐서 가는 경로가 빠르다면,
더 빠른 경로를 업데이트해준다.
이게다다.
##플로이드알고리즘!!!import sysinput=sys.stdin.readlinen=int(input())bus=int(input())
##arr[i][j]는 i에서j로 가는 최소비용
arr=[[0 if i==j else 1e+8 for i in range(n)]for j in range(n)]# 0은 제외니 -1해주기
for _ in range(bus): a,b,c=map(int,input().split()) a-=1 b-=1
arr[a][b]=min(arr[a][b],c)#여기까지 arr완성#플로이드알고리즘for k in range(n):
for i in range(n): for j in range(n): if i==j:continue
if arr[i][j]>arr[i][k]+arr[k][j]:
arr[i][j]=arr[i][k]+arr[k][j]for i in range(n):
for j in range(n): if arr[i][j]==1e+8: print(0,end=' ')
else: print(arr[i][j],end=' ') print()p.s
알고리즘에 대해서 한참 고민했던것이, i,j가 아직 업데이트되지 않았을때의 경로가 최소경로일 경우를 못구할 것 같았다.
하지만, 쓸데없는 걱정이였다.
배열에는 이미 이전 모든k를 거쳤을때의 최솟값이 업데이트되어있을것이다.
k를 두번 거칠 일은 절대 없으므로(상식상)
반복문이종료된 후에는 모든 값이 최소경로를 나타내게 된다!!