[python] 백준 17835 면접보는 승범이네

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

17835번: 면접보는 승범이네

 

문제 해결

• 다익스트라를 이용해야 한다는 것은 쉽게 알 수 있다.
• 그러나 출발점→도착점 이동을 모두 계산하기에는 계산해야하는 양이 많아 시간복잡도에서 걸린다.
• 따라서 도착점에서 시작해서 각 출발점까지 얼마나 걸리는지 계산하는 것이 더 빠르다.

 

CODE

import sys
input = sys.stdin.readline
import heapq

def dijkstra():
    heap = []
    for t in targets: # 출발지
        heapq.heappush(heap,(0,t))
        result[t] = 0
    
    while heap:
        cost, city = heapq.heappop(heap)
        if result[city] < cost: continue
        for next_cost, next_city in graph[city]:
            if cost + next_cost < result[next_city]:
                result[next_city] = cost+next_cost
                heapq.heappush(heap, (cost+next_cost,next_city))
                
        
if __name__=='__main__':
    n, m, k = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u, v, c = map(int, input().split())
        graph[v].append((c,u))
    targets = list(map(int, input().split()))
    max_start, max_cost= 0, 0
    result = [int(1e11) for _ in range(n+1)]
    dijkstra()
    for i, r in enumerate(result):
        if r> max_cost and r != int(1e11):
            max_start, max_cost = i, r
    print(max_start)
    print(max_cost)