one Book a Day

플로이드 워셜 기본문제 각 기점에 대해 모든 경로를 전수조사한다. 한번당 기점 하나를 거치는 경로이다. import sys input = sys.stdin.readline n, m = int(input()), int(input()) bus_datas = [[float('inf')] * n for _ in range(n)] for _ in range(m): a, b, c = map(int, input().split()) bus_datas[a - 1][b - 1] = min(bus_datas[a - 1][b - 1], c) for k in range(n): bus_datas[k][k] = 0 for i in range(n): for j in range(n): if bus_datas[i][j] > bus_da..

최단거리 문제연습. 모든 정점에서 모든 정점. 주의 할 점은 동일 출발, 동일 도착 간선이 있고 때문에 입력 시 최솟값만을 입력해주어야함. 플로이드 워샬은 간선이 없는 전 구간에 대해 조사하기 때문에 사실 인접리스트의 의미가 좀 없는 것 같다. 인접행렬로 표현하는게 더 효율저일듯 싶다. import sys input = sys.stdin.readline def floid_washal(): dp_dists = [[float('inf') for _ in range(n+1)] for _ in range(n+1)] for cur_node in graph: for next_node,dist in graph[cur_node]: if dp_dists[cur_node][next_node] > dist: dp_dists..