- 빠른 입력 코드
import sys
input = sys.stdin.readline
#이후에 input()으로 사용
#입력 후 한줄개행의 경우 .rstrip() 사용- 시간측정코드
import time
start_time = time.time()
end_time = time.time()
print(end_time - start_time)- 문자 -> 숫자 변환코드
int(ord(input_data[0])) - int(ord('a'))- 이중탐색코드
def binary_search(array, target, start, end) :
if start > end :
return None
mid = (start+end)//2
if target == array[mid] :
return mid
elif target < array[mid] :
return binary_search(array, target, start, mid-1)
else :
return binary_search(array, target, mid+1, end)- 다익스트라
import heapq
import sys
INF = int(1e9)
input = sys.stdin.readline
#노드의 개수, 간선의 개수
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
#간선 입력
for _ in range(m) :
a, b, c = map(int, input().split()) #a->b 간선의 비용 : c
graph[a].append((b, c))
def dijkstra(start) :
#큐를 설정하여 시작점을 큐에 넣는다
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
#큐가 빌때까지 반복하여 실시한다
while q :
#최단거리, 해당 노드를 가져온다
dist, now = heapq.heappop(q)
#이미 처리된 값인 경우 무시한다
if distance[now] < dist :
continue
#인접한 노드 개수만큼 반복한다
for i in graph[now] :
cost = dist + i[1] #i[0] : 노드값, i[1] : 간선비용
#갱신값이 작은경우 갱신한다
if cost < distance[i[0]] :
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(start)
for i in range(1, n+1) :
if distance[i] == INF :
print("INFINITY")
else :
print(distance[i])- 플로이드 워셜
INF = int(1e9)
#노드수, 간선수
n = int(input())
m = int(input())
#무한으로 초기화
graph = [[INF]*(n+1) for _ in range(n+1)]
#시작 = 종료 간선값을 0으로 저장
for a in range(1, n+1) :
for b in range(1, n+1) :
if a == b :
graph[a][b] = 0
#a->b : 간선 c
for _ in range(m) :
a, b, c = map(int, input().split())
graph[a][b] = c
#현재값과 현재를 거치는 모든경우를 계산하여 최소값으로 갱신한다
for k in range(1, n+1) :
for a in range(1, n+1) :
for b in range(1, n+1) :
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
#N*N 전체 경우를 출력한다
for a in range(1, n+1) :
for b in range(1, n+1) :
if graph[a][b] == INF :
print("INFINITY", end=" ")
else :
print(graph[a][b], end=" ")
print()