문제 풀러 가기!

전형적인 PS 풀이를 이용한 문제입니다.
G1에 랭크되어 있는 만큼 알고리즘 짜기 힘들기도 하고 생각하기도 힘들다는 생각이 드네요.

그래도 괜찮습니다. 차근차큰 생각하다보면, 답이 나올 것입니다.

문제에서 설명하기를 1번은 인터넷이 무조건 연결되어 있고 N번째를 연결하고 싶다고 합니다. 각각의 번호는 모두 노드이고, 노드를 잇기 위한 cost도 존재하고 있습니다.

그리고 사장님이 k개 이상 연결된 간선에 대해서 돈을 지출해야 되는데, 이때 지출할 돈의 최소값을 찾는 문제입니다.

시간 복잡도 생각하기

돈의 최소값을 찾아야 하며, 주어진 데이터가 생각보다 많기 때문에(간선 개수만 10,000개, 가중치의 최대값 1,000,000) 이분 탐색을 시도해야 합니다. 그리고 한번 순회를 할 때 최대 10,000개를 모두 돌아다닐 수 있으며 어떤 값이 가장 최적인지 찾기 위해서는 최악으로 1,000,000 * 10,000의 시간복잡도가 나올 수 있습니다. 그러면, 이걸 어떻게 줄일 수 있을까요?

바로 dijkstra입니다. dijkstra로 순회하면 (노드의 개수)log(간선의 개수) log(n) → 1000 𝗑 log(10,000) 𝗑 log(1,000,000) 입니다.

즉, 약 1800만 정도의 순회 끝에 모든 순회를 마칠 수 있습니다.

사장이 지출할 값들의 최대값 중 최소값을 찾아야 하므로 이 지출 상한을 이분 탐색으로 찾습니다. 이때 dijkstra로 지출할 값이 target한 값보다 큰 녀석들을 count합니다. 그리고 count한 값이 k(무료 개수)보다 크다면, 지출 상한을 높여주고 그렇지 않다면 지출 상한을 낮춰줍니다. 그리고 이렇게 찾은 지출 상한이 바로 답이 됩니다.

주의: 못찾으면 -1을 출력해야함.

코드 💻

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

n, p, k = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(p):
    s, e, c = map(int, input().split())
    graph[s].append((e, c))
    graph[e].append((s, c))


def dijkstra(start):

    INF = 10001
    dist = [INF] * (n+1)
    dist[start] = 0

    pq = []
    heappush(pq, (0, start))

    while pq:
        cost, now = heappop(pq)

        if cost > dist[now]: continue

        for nxt, c in graph[now]:
            if c > mid:
                if dist[nxt] > 1 + cost:
                    dist[nxt] = 1 + cost
                    heappush(pq, (1 + cost, nxt))
            else:
                if dist[nxt] > cost:
                    dist[nxt] = cost
                    heappush(pq, (cost, nxt))

    return dist
  
start = 0
end = 100000001
answer = 100000001
while start <= end:
    
    mid = (start + end) // 2
    result = dijkstra(1)

    if result[n] > k:
        start = mid + 1
    elif result[n] <= k:
        answer = mid
        end = mid - 1

if answer == 100000001:
    print(-1)
else:
    print(answer)