[백준 알고리즘] 16167번: A Great Way (Python)

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

16167번: A Great Way

 

소스코드

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:
    cost,node = hq.heappop(q)

    if min_dis[node] < cost:
      continue

    for n_node,basic,extra,time in graph[node]:
      # 비용 계산 !! 
      if time >= 10: 
        charge = basic + (time-10)*extra
      else:
        charge = basic
      # 최소 비용으로 갈 수 있도록 갱신
      if min_dis[n_node] > charge+cost: 
        min_dis[n_node] = charge+cost
        pre_v[n_node] = node # 거점의 수를 알기 위해 pre_v라는 리스트에 거점 입력
        hq.heappush(q,[charge+cost,n_node])

  return min_dis

n,r = map(int,input().split())
graph = [[] for _ in range(n+1)]
pre_v = [n] * (n+1)
for _ in range(r):
  a,b,c,d,e = map(int,input().split())
  # 최소 비용 경로가 여러가지 존재하면 거점의 수를 최소로 가기 위해 그래프를 역방향으로 그림
  graph[b].append([a,c,d,e]) 

t = dijkstra(n)
path = [1] # 정점을 역추적하면서 몇개의 정점을 방문했는지 확인 
now = 1
while now != n:
  now = pre_v[now]
  path.append(now)

if t[1] == float('inf'):
  print('It is not a great way.')
else:
  print(t[1],len(path))

 

풀이

★ 핵심은 최소 비용 경로가 여러 가지 존재하면 방문하는 정점의 수를 최소화하여 출력하는 것입니다. 그렇기에 저는 목적지에서부터 출발지까지 역으로 탐색하며 다익스트라를 진행하였습니다.

 

★이 때, 방문한 거점의 수를 확인하기 위해 방문할 때마다 pre_v라는 리스트에 정점을 확인해줬습니다. 그 이후 역추적하면서 방문한 정점의 수를 출력했습니다 ! 

 

★정점간에 이동할 때 비용을 계산하는 것도 잘 확인하셔야 합니다 ! 10분마다의 요금이 아닌, 첫 10의 기본요금이며 그 이후의 시간들은 시간당 요금으로 측정하셔야 합니다 :)