BOJ - 1800

백준 문제 링크
인터넷 설치

❓접근법

1. 다익스트라 알고리즘 + 이분 탐색 알고리즘을 활용했다.
2. 다익스트라 함수 (money) 내에서,
   for i, cost in graph[now]의 반복문 동안

• if cost > mid:
  • if distance[i] > 1 + dist:
    distance[i] = 1 + dist
    heapq.heappush(q, (1 + dist, i))
• else:
  • if distance[i] > dist:
    distance[i] = dist
    heapq.heappush(q, (dist, i))

3. 이제, start = 0, end = 100000001, answer = INF로 지정하고
   이분 탐색을 해서 최소의 돈을 찾아줄 것이다.
   이분 탐색 코드에서 result = money(1)로 지정한다.

• if result[n] > k:
  • start = mid + 1
• else:
  end = mid - 1
  answer = mid
  이 조건은 지출할 값의 최대 중 최소를 찾는 것이다.

4. 마지막으로 answer == INF이면 -1을, 아니면 answer를 출력한다.

👌🏻코드

import heapq

INF = int(1e9)
n, p, k =  map(int, input().split())

graph = [[] for _ in range(n + 1)]

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

def money(start):
    
    distance = [INF] * (n + 1)
    
    q = []
    
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        
        if distance[now] < dist:
            continue
            
        for i, cost in graph[now]:
            
            if cost > mid: 
                if distance[i] > 1 + dist:
                    distance[i] = 1 + dist
                    heapq.heappush(q, (1 + dist, i))
                    
            else:
                if distance[i] > dist:
                    distance[i] = dist
                    heapq.heappush(q, (dist, i))
                    
            
            
                
    return distance

start, end, answer = 0, 100000001, INF

while start <= end:
    
    mid = (start + end) // 2
    result = money(1) 

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

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

진짜 너무 어려웠다...
너무 친절하게 설명해주신 분이 있어서 다행이다... 인터넷 설치 설명 링크