[Python] 백준 최단경로

 

 

문제

방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

​

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤ V ≤20,000, 1≤ E ≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤ K ≤ V)가 주어진다. 셋째 줄부터 E 개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V 개의 줄에 걸쳐, i 번째 줄에 i 번 정점으로의 최단 경로의 경로 값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

​

​

성공

​

input() 이 시간 초과가 발생

input()은 사용자의 입력을 받고 → 문자열로 변환 → 추가 strip 진행 의 과정을 거침

입력 없는데 수행될 경우 에러 발생

sys.stdin.readline()

사용자의 입력만을 받는 buffer를 하나 만들어 그 buffer에서 읽어들이는 것

빈 문자열 반환, 더 빠름

 

import heapq  # 힙구조 사용 
import sys # input은 내장함수고 이거는 따로 생성해줘야함 

# 입력 받음  정점, 간선
v,e =map(int,sys.stdin.readline().split())
k=int(sys.stdin.readline())

# 가장 최댓값으로 지정 (결과값 출력하는 변수)
result=[ 200000 for i in range(v+1)]

result[k]=0 # 처음 시작값 0으로 설정
dis=[[] for _ in range(v+1)] # 각 값들 넣는 곳 
for _ in range(e):#간선받아서 그래프에 저장
    start,end,d=map(int,sys.stdin.readline().split())
    # 값 입력
    # 해당 위치에 이동하는 값,이동하는 위치 
    dis[start].append([d,end])

que=[]# 계산 하는 큐 
heapq.heappush(que,[0,k])# 처음 시작값은 0으로 시작 

# que 에 계산
while que:
    # 값을 가져오고 (힙은 알아서 정렬) 
  w,end=heapq.heappop(que)
  for d,x in dis[end]: # 해당하는 값 가져옴
    d+=w # 이동한 값 
    if d<result[x]: # 작을 경우 최종 결과 바꿔줌
      result[x]=d
      heapq.heappush(que,[d,x]) # 다시 큐에 넣음 계산

 #계산 
for i in range(1,v+1):
    # 200000일 경우, 이동할 수 있는 경로 없다는 것
  if result[i]==200000:
    print('INF') # InF출력
  else:
    print(result[i]) # 아니면 경로 있음 출력