8/28 (다익스트라 연습하기, 최단경로 이코테 풀기)

1753번: 최단경로

이코테를 풀기 전 한번더 풀어봅시다…

다익스트라 알고리즘 아무것도 참조하기 않고 푸는 것에 아직 너무 약하다 익숙해지자.

import sys
import heapq

input = sys.stdin.readline
distances = []

INF = int(1e9)

V, E = map(int, input().split())
K = int(input())
distances = [INF] * (V + 1)
graph = [[] for _ in range(V + 1)]

for _ in range(E):
  u, v, w = map(int, input().split())
  graph[u].append((v, w))

hq = []
distances[K] = 0
heapq.heappush(hq, (0, K))

while hq:
  data = heapq.heappop(hq)
  dist, now = data

  if distances[now] < dist:
    continue

  for ele in graph[now]:
    nV = ele[0]
    cost = ele[1] + dist

    if cost < distances[nV]:
      distances[nV] = cost
      heapq.heappush(hq, (cost, nV))

for i in range(1, V + 1):
  if distances[i] == INF:
    print('INF')
  else:
    print(distances[i])

또 한번 더 풀어봅시다

import sys
import heapq

sys = sys.stdin.readline
INF = int(1e9)

V, E = map(int, input().split())
K = int(input())
distances = [INF] * (V + 1)
graph = [[] for _ in range(V + 1)]

for _ in range(E):
  u, v, w = map(int, input().split())
  graph[u].append((v, w))

def dijktra():
  hq = []

  distances[K] = 0
  heapq.heappush(hq, (0, K))

  while hq:
    dist, now = heapq.heappop(hq)

    if distances[now] < dist:
      continue

    for i in graph[now]:
      cost = dist + i[1]
      nV = i[0]

      if cost < distances[nV]:
        distances[nV] = cost
        heapq.heappush(hq, (cost, nV))

dijktra(K)

for i in range(1, V + 1):
  if distances[i] == INF:
    print('INF')
  else:
    print(distances[i])

시간초과가 납니다.

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)

V, E = map(int, input().split())
K = int(input())
distances = [INF] * (V + 1)
graph = [[] for _ in range(V + 1)]

for _ in range(E):
  u, v, w = map(int, input().split())
  graph[u].append((v, w))

def dijktra():
  hq = []

  distances[K] = 0
  heapq.heappush(hq, (0, K))

  while hq:
    dist, now = heapq.heappop(hq)

    if distances[now] < dist:
      continue

    for i in graph[now]:
      cost = dist + i[1]
      nV = i[0]

      if cost < distances[nV]:
        distances[nV] = cost
        heapq.heappush(hq, (cost, nV))

dijktra()

for i in range(1, V + 1):
  if distances[i] == INF:
    print('INF')
  else:
    print(distances[i])

보니까 sys를 이용하지 못하게 코드를 실수로 작성했다.

sys를 적용하지 않고 input을 그대로 사용하니 시간초과가 났다.

sys를 무조건 적용해야 한다는 교훈을 얻었다 ㅎㅎ..!