# 최단경로
import sys
INF = int(1e9)
V, E = map(int,sys.stdin.readline().split())
K = int(sys.stdin.readline())
# 그래프 표현
graph = [[] for _ in range(V+1)]
visited = [False] * (V+1)
weight = [INF] * (V+1)
# 가중치 입력
for _ in range(E):
u,v,w = map(int,sys.stdin.readline().split())
graph[u].append((v,w)) # 이웃 노드 저장
# 최단 거리 노드 찾는 함수
def get_smallest_node():
min_value = INF
index = 0
for i in range(1,V+1): # 1번째 노드부터 탐색하며 최단거리 노드를 찾는다.
if not visited[i] and weight[i] < min_value: # 아직 방문하지 않은 노드이면서 최단거리인 노드
min_value = weight[i]
index = i
return index
# 다익스트라 알고리즘
def dijkstra(K):
# 시작노드
weight[K] = 0 # 자기자신의 가중치는 0
visited[K] = True # 방문처리
# 시작노드와 인접한 노드들의 최단거리 계산
for g in graph[K]:
weight[g[0]] = g[1]
# 시작노드를 제외한 다른 노드들 처리 -> V-1 개
for _ in range(V-1):
now = get_smallest_node()
visited[now] = True # 방문처리
# 해당노드의 인접한 노드들의 가중치 계산
for g in graph[now]:
w = weight[now] + g[1]
# 기존 가중치와 비교 후 새로 계산한 값이 더 작으면 값 업데이트
if w < weight[g[0]]:
weight[g[0]] = w
dijkstra(K)
for i in range(1,V+1):
if weight[i] == INF:
print("INF")
else:
print(weight[i])
시간초과 발생 -> heapq 사용
# 최단경로
import sys
import heapq
INF = int(1e9)
V, E = map(int,sys.stdin.readline().split())
K = int(sys.stdin.readline())
# 그래프 표현
graph = [[] for _ in range(V+1)]
weight = [INF] * (V+1)
weight[K] = 0 # 시작노드는 자기자신이므로 가중치 값이 0이다
# 가중치 입력(입력값)
for _ in range(E):
u,v,w = map(int,sys.stdin.readline().split())
graph[u].append([v,w]) # 이웃 노드 저장
# heapq에 가중치 저장
heap = []
heapq.heappush(heap,[K,0]) # 시작노드의 가중치는 0
# 다익스트라 알고리즘
def dijkstra():
while heap:
now, now_weight = heapq.heappop(heap) # 탐색할 노드, 가중치
if weight[now] < now_weight: # 가중치 값 비교
continue
for new, new_weight in graph[now]:
final_weight = now_weight + new_weight
# 기존 가중치와 비교 후 새로 계산한 값이 더 작으면 값 업데이트
if final_weight < weight[new]:
weight[new] = final_weight
heapq.heappush(heap,[new,final_weight])
dijkstra()
for i in range(1,V+1):
if weight[i] == INF:
print("INF")
else:
print(weight[i])
4% 시간초과........
# 최단경로
import sys
import heapq
INF = int(1e9)
V, E = map(int,sys.stdin.readline().split())
K = int(sys.stdin.readline())
# 그래프 표현
graph = [[] for _ in range(V+1)]
weight = [INF] * (V+1)
weight[K] = 0 # 시작노드는 자기자신이므로 가중치 값이 0이다
# 가중치 입력(입력값)
for _ in range(E):
u,v,w = map(int,sys.stdin.readline().split())
graph[u].append([w,v]) # 이웃 노드 저장
# heapq에 가중치 저장
heap = []
heapq.heappush(heap,[0,K]) # 시작노드의 가중치는 0
# 다익스트라 알고리즘
def dijkstra():
while heap:
now_weight,now = heapq.heappop(heap) # 탐색할 노드, 가중치
if weight[now] < now_weight: # 가중치 값 비교
continue
for new_weight,new in graph[now]:
final_weight = now_weight + new_weight
# 기존 가중치와 비교 후 새로 계산한 값이 더 작으면 값 업데이트
if final_weight < weight[new]:
weight[new] = final_weight
heapq.heappush(heap,[final_weight,new])
dijkstra()
for i in range(1,V+1):
if weight[i] == INF:
print("INF")
else:
print(weight[i])
도움 https://www.acmicpc.net/board/view/64342
heapq에 삽입할 때 가중치값이 우선순위가 되어야 한다.
=> heapq.heappush(heap,[가중치,노드값]) 이렇게 되어야함