플로이드 워셜 알고리즘

코드 # 모든 노드에서 모든 노드로 가는 경우를 찾아야하므로 플로이드 워셜 알고리즘 사용 # 알파벳 대소문자는 총 52개라서 O(N^3)인 알고리즘 사용 가능 import sys input = sys.stdin.readline INF = 987654321 n = int(input()) graph = [[INF]*59 for _ in range(59)] # ord를 이용할 것이라 59개로 만들어주었음 for _ in range(n): x,y = input().rstrip().split(" => ") graph[ord(x)-64][ord(y)-64] = 0 # 단방향 그래프 def floyd(): for i in range(59): for j in range(59): for k in range(59): if..

코드 import sys input = sys.stdin.readline INF = 987654321 v,e = map(int, input().split()) graph = [[INF]*(v+1) for _ in range(v+1)] for _ in range(e): x,y,z = map(int, input().split()) graph[x][y] = z def floyd(): # 플로이드 워셜 알고리즘 for i in range(1,v+1): for j in range(1,v+1): for k in range(1,v+1): # 자기 자신에게 돌아오는 사이클을 찾아야하므로 j==k일 때 넘겨주는 코드 생략 graph[j][k] = min(graph[j][k], graph[j][i]+graph[i][k])..