백준 1800 인터넷 설치

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

해결하지 못해 다른사람들의 풀이를 참조했다.

이 문제는 다익스트라 + 이분탐색 문제이다.
다익스트라와 이분탐색에 대해 이해해야 위 문제를 풀 수 있었다.

어떤 조건을 만족하는 최대, 최소값 문제에서는 어떤 지점에서 pivot이 생겨 이분적으로 값이 나뉘는지를 확인해야 함을 알게되었다.

위 문제에서는 특정 가격을 x라고 했을때
조건(x)가 참인 경우에는 연결이 불가하고,
조건(x)가 거짓인 경우에는 연결이 가능하다.
그렇기 때문에 위의 조건을 만족하는 x값을 이분탐색으로 찾으면 된다.

x값의 조건은 다익스트라를 통해 최단거리로 연결했을때 이용되는 인터넷 선의 갯수를 구하면 된다.

import math
import heapq

def dijkstra(start,limit):

    distance = [math.inf]*(n+1)
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cur_dist, cur_des = heapq.heappop(q)
        if distance[cur_des] < cur_dist:
            continue

        for node in graph[cur_des]:
            if node[1] > limit:
                if cur_dist + 1 < distance[node[0]]:
                    distance[node[0]] = cur_dist + 1
                    heapq.heappush(q, (cur_dist + 1, node[0]))
            else:
                if cur_dist < distance[node[0]]:
                    distance[node[0]] = cur_dist
                    heapq.heappush(q, (cur_dist, node[0]))
    if distance[n] > k:
        return False
    else:
        return True

n,p,k = list(map(int,input().split()))
graph = [[] for i in range(n+1)]
for i in range(p):
    a,b,c = list(map(int,input().split()))
    graph[a].append((b,c))
    graph[b].append((a,c))

lo, ro = -1, 1000001
ans = math.inf
while lo + 1 < ro:
    mid = (lo + ro) // 2
    res = dijkstra(1,mid)
    if res:
        ro = mid
        ans = ro
    else:
        lo = mid
if ans == math.inf:
    print(-1)
else:
    print(ans)