코드 import heapq, sys input = sys.stdin.readline INF = 987654321 # 다익스트라 알고리즘 def dijkstra(x,graph): visited = [INF]*(n+1) queue = [(0,x)] visited[x] = 0 while queue: cost, now = heapq.heappop(queue) if cost > visited[now]: continue for i in graph[now]: newcost = cost + i[1] if visited[i[0]] > newcost: visited[i[0]] = newcost heapq.heappush(queue, (newcost, i[0])) return visited tc = int(input())..
다익스트라
코드 1 (0-1 BFS 풀이) from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [input() for _ in range(m)] visited = [[0]*n for _ in range(m)] def bfs(): # 가중치가 0 또는 1만 있기 때문에, 0-1 bfs가 떠올랐다. queue = deque([(0,0)]) dx, dy = [1,-1,0,0],[0,0,1,-1] # 이동할 수 있는 경우의 수 visited[0][0] = 1 # 첫번째 노드 방문기록을 해준다 while queue: popx, popy = queue.popleft() if popx ..
# 노드 개수가 1000개라 플로이드 워셜 사용 불가, 양의 간선만 존재 # 다익스트라 사용 import sys, heapq input = sys.stdin.readline INF = 987654321 n = int(input()) m = int(input()) graph = [[] for _ in range(n+1)] visited = [INF] *(n+1) for _ in range(m): x,y,z = map(int, input().split()) graph[x].append((y,z)) start, end = map(int, input().split()) path = [0]*(n+1) # 경로추적을 위한 방문기록표 def dijkstra(start): queue = [(0, start)] visi..
코드 # 노드의 개수가 20000개이므로 시간복잡도가 O(N^3)인 플로이드-워셜은 효율이 낮다. # 가중치는 10 이하의 자연수이므로 다익스트라를 사용할 수 있다. # O(Elogv)로 해결 가능 import sys, heapq # 우선순위 큐를 이용한 다익스트라를 구현할 것이므로 heapq모듈 사용 INF = 987654321 input = sys.stdin.readline n,m = map(int, input().split()) k = int(input()) graph = [[] for _ in range(n+1)] # 입력하기 쉽게 (n+1)로 해주었음 visited = [INF]*(n+1) # 방문 경로 for _ in range(m): x,y,z = map(int, input().split()..
코드 import sys, heapq input = sys.stdin.readline INF = 987654321 n = int(input()) m = int(input()) graph = [[] for _ in range(n+1)] visited = [INF]*(n+1) # 방문 기록을 위해 1차원 배열 생성 for _ in range(m): x,y,z = map(int, input().split()) graph[x].append((y,z)) startpoint, dist = map(int, input().split()) def dijkstra(start): q = [(0, start)] visited[start] = 0 while q: popstart, popdist = heapq.heappop(q)..
