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

문제

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

17835번: 면접보는 승범이네

풀이

도시의 개수만큼 다익스트라 계산하면 대략 10억번의 연산이 수행되어 시간초과가 나온다. 

모든 도시에서 면접장으로 갈 수 있는 경로가 항상 있음 -> 면접장에서 도시로 향하는 다익스트라 가능

-> 도시의 연결 정보 입력 시 역방향으로 관계 지정해야 함. (도시: arr / 면접장: targets)

다익스트라에서 탐색 할 도시 리스트 h에 각 면접장 모두 넣어주고 수행

코드

import sys
import heapq
N, M, K = map(int, sys.stdin.readline().split())
arr = [[] for _ in range(N+1)]
for i in range(M):
    a, b, cost = map(int, sys.stdin.readline().split())
    arr[b].append([a, cost])

targets = list(map(int, sys.stdin.readline().split()))


def dijkstra():
    h = []
    for t in targets:
        heapq.heappush(h, [0, t])
        result[t] = 0
    while h:
        cost, city = heapq.heappop(h)
        if result[city] < cost:
            continue
        for next_city, next_cost in arr[city]:
            if cost + next_cost < result[next_city]:
                result[next_city] = cost+next_cost
                heapq.heappush(h, [cost+next_cost, next_city])


max_start, max_cost = 0, 0
result = [int(1e11)] * (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)