백준/최단경로
# 1753 최단 경로 파이썬
bright_code
2021. 4. 9. 21:49
728x90
반응형
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.
www.acmicpc.net
import sys
import heapq
input = sys.stdin.readline
V,e = map(int,input().split()) # 정점, 간선
k = int(input()) # 시작
graph = [ [] for _ in range(V+1)]
for i in range(e):
u,v,w = map(int,input().split())
graph[u].append( (v,w) ) # 이어진 곳, 거리
# 경로 존재하지 않으면 INF
def dij(start):
q = []
dist = [1e9]*(V+1)
heapq.heappush(q, (0,k) )
dist[start]=0
while q:
d, now = heapq.heappop(q)
if dist[now]< d : continue # 전에 방문한 적 있으면 처리하지 않음
for i in graph[now]:
cost = d + i[1]
if cost < dist[i[0]] :
dist[i[0]] = cost
heapq.heappush(q, (cost,i[0]))
return dist
result = dij(k)
for i in range(1,V+1):
if result[i] == 1e9 :
print("INF")
else:
print(result[i])
정점 대문자 V
중간에 입력 받는거 소문자 v....
728x90
반응형