[백준 알고리즘] 17835번: 면접보는 승범이네 (Python)

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

17835번: 면접보는 승범이네

 

소스코드

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

def dijkstra():
  q = []
  min_dis = [float('inf') for _ in range(n+1)]
  for i in test: # 우선순위 큐에 한번에 다 넣고 실행 
    min_dis[i] = 1
    hq.heappush(q,[0,i])
  
  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,k = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m): # 면접장에서 각각의 도시로 가는 역방향으로 간선을 그어줌
  a,b,c = map(int,input().split())
  graph[b].append([a,c])

test = list(map(int,input().split()))
cities = []
ans = -float('inf')

t = dijkstra()

for i in range(1,n+1):
  if t[i] > ans:
    ans = t[i]
    result = i
print(result)
print(ans)

 

풀이

★ 양방향 간선이 아닌 단방향이기 때문에 면접장에서 도시로 가는 역발상을 떠올렸다고 해도, 이동할 수 없는 경우가 존재합니다 ! 그렇기에 그래프를 만들 때 a,b,c가 주어진다면 a -> b로 c동안 가는 그래프가 아닌 b -> a로 c만큼 가는 그래프를 그려줘야 합니다. 

 

★ 또한 도시에서 면접장까지의 거리를 구하기 위해 다익스트라를 n번 수행하게 된다면 당연히 시간초과가 나오게 됩니다. 그렇기에 면접장이 있는 도시를 우선순위 큐에 한번에 집어넣는다면 한번의 다익스트라로 결과값을 도출할 수 있습니다:)