Algorithm/백준

[백준 알고리즘] 5590번: 船旅 (Python)

에릭 Kim 2023. 12. 20. 14:38
반응형

https://www.acmicpc.net/problem/5590

 

5590번: 船旅

入力の 1 行目には2つの整数 n, k (1 ≦ n ≦ 100, 1 ≦ k ≦ 5000) が書かれている． これは，島の数が n 島で，入力が k + 1 行からなることを表す．  i + 1 行目 (1 ≦ i ≦ k) には， 3 個または 4 個の

www.acmicpc.net

 

소스코드  

import sys
import heapq as hq
input = sys.stdin.readline

def dijkstra(start):
  q = []
  min_dis = [float('inf') for _ in range(n+1)]
  min_dis[start] = 0
  hq.heappush(q,[0,start])

  while q:
    cur_dis,cur_node = hq.heappop(q)

    if min_dis[cur_node] < cur_dis:
      continue

    for next_node,next_dis in graph[cur_node]:
      if min_dis[next_node] > next_dis + cur_dis:
        min_dis[next_node] = next_dis + cur_dis
        hq.heappush(q,[next_dis+cur_dis,next_node])

  return min_dis

n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
  a = list(map(int,input().split()))
  if a[0] == 0:
    k = dijkstra(a[1])
    if k[a[2]] == float('inf'):
      print(-1)
    else:
      print(k[a[2]])
  elif a[0] == 1:
    graph[a[1]].append([a[2],a[3]])
    graph[a[2]].append([a[1],a[3]])

 

풀이

★ 문제가 일본어로 되어있어서 파파고로 번역해서 풀었습니다 !! 먼저 문제를 선택한 이유는 다익스트라 구현을 똑같지만, 입력 값으로 0 or 1이 들어왔을 때, 그 값대로 수행해야 하는 조건이 다르다는 점이 새로웠습니다.

 

★ 0이 들어오면 기존에 존재하는 그래프만으로 다익스트라를 수행하여 결과값을 도출하면 되고, 1이 들어올 경우 그래프를 새롭게 갱신한 뒤, 이 후에 0이 들어올 때 갱신된 그래프를 기준으로 답을 도출해야 합니다 :) 

반응형