20183 골목 대장 호석 (파이썬)

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

문제 풀이 

1. 최단거리로 이동하되 그 과정에서 나오는 비용 중 최대 비용이 가장 작은 거리를 찾는 문제.

2. 다익스트라로 최단 거리를 찾아가는 과정.

3. 이때 힙큐의 우선 순위로 둘 수 있는 것은 (최단 거리 비용과 최대 비용)중 하나인데 노드의 갯수가 10만, 루트의 갯수가 50만이므로 도착 지점에 도달했을 경우 탐색 과정이 끝나는 것이 좋다. 때문에 정답이 되는 최대 비용을 힙큐의 우선순위로 두어서 도착 지점일 경우 반복문이 끝나도록 하면 된다.

 4. 힙큐에는 [ 이동하면서 발견한 최댓값, 거리 가중치, 현재 위치 ] 를 삽입

5. 방문했던 것들을 기록하기 위해 visited를 선언. visited에는 각 노드별 [ 최단 거리 가중치, 최대 비용 ] 을 기록한다.

6. 다음 노드에 갈 수 있는지 체크할 때

 1) 다음까지의 거리 가중치가 visited[다음 노드] [최단 거리 가중치] 보다도 작다면 최대 비용이 더 크더라도 나중에 또 탐색은 해야하니 힙큐에 넣어준다.

 2) 다음 노드까지 가는데 드는 최대 비용이 기록되어 있는 visited[다음 노드][최대비용] 보다 작다면 거리 가중치가 제한보다 작다면 정답이 될 수 있으므로 이또한 힙큐에 넣어준다.

while hq:
    max_edge, cur_cost, node = heapq.heappop(hq)

    if node == end:
        answer = min(answer, max_edge)
        break

    for neighbor, weight in graph[node]:
        next_cost = cur_cost + weight
        if next_cost > limit:
            continue
        next_max = max(max_edge, weight)

        if visited[neighbor][0] > next_cost or visited[neighbor][1] > next_max:
            visited[neighbor][0] = next_cost
            visited[neighbor][1] = next_max
            heapq.heappush(hq, (next_max, next_cost, neighbor))

정답 코드

import sys
import heapq

input = sys.stdin.readline

n, m, start, end, limit = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))

INF = 10**14
visited = [[INF, INF] for _ in range(n + 1)]
hq = []
heapq.heappush(hq, (0, 0, start))  # (max_edge_weight, total_cost, current_node)
visited[start] = [0, 0]

answer = INF

while hq:
    max_edge, cur_cost, node = heapq.heappop(hq)

    if node == end:
        answer = min(answer, max_edge)
        break

    for neighbor, weight in graph[node]:
        next_cost = cur_cost + weight
        if next_cost > limit:
            continue
        next_max = max(max_edge, weight)

        if visited[neighbor][0] > next_cost or visited[neighbor][1] > next_max:
            visited[neighbor][0] = next_cost
            visited[neighbor][1] = next_max
            heapq.heappush(hq, (next_max, next_cost, neighbor))

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