dist[v] = 시작점→v까지 경로 중 최소 간선값의 최댓값- 시작점은 제약이 없으므로
dist[start] = float('inf') 로 두고 최대 힙(음수화)으로 탐색하기
- 힙에서 꺼낸 weight보다 작은 구버전 경로는 무시하기
- 이웃 탐색 시
new_w = min(weight, w)로 병목(최소 간선값) 갱신, 기존보다 크면(최댓값 찾아야 하므로) dist와 힙 갱신하기
from collections import defaultdict
import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = defaultdict(list)
for i in range(M):
line = list(map(int, input().split()))
a, b, c = line[0], line[1], line[2]
graph[a].append((b, c))
graph[b].append((a, c))
f1, f2 = map(int, input().split())
# 지금까지의 경로 가중치 중 최소 간선값을 최대화하기
def max_dijkstra(start):
# dist[v]: 시작점에서 v까지 갈 수 있는 경로들 중 최소 간선값의 최댓값
dist = [-float("inf")] * (N + 1)
# 출발점은 아직 최소값 제한이 없으므로 무한대로 초기화 해야함 주의!! (0으로 설정하면 모든 dist가 항상 0 됨)
dist[start] = float("inf")
heap = []
heapq.heappush(heap, (-dist[start], start)) # 최대 힙 구현을 위해 -붙여서 넣기!
while heap:
weight, node = heapq.heappop(heap)
weight = -weight # 음수를 양수로 바꿔줘야 함 주의!!
# 도착지에 도착 시 종료
if node == f2:
break
# 구버전은 무시하기(현재 값보다 더 작은 경로라면)
if weight < dist[node]:
continue
for c, w in graph[node]:
new_w = min(weight, w) # 현재까지의 간선들 중 최소 간선값
# 기존의 최소 간선값의 최댓값(dist[c])보다 현재 값이 더 크면 갱신
if new_w > dist[c]:
dist[c] = new_w
# 힙에 weight 넣을 땐 음수로 넣기!(최대 힙)
heapq.heappush(heap, (-new_w, c))
# 시작점(f1)에서 도착지(f2)까지 갈 수 있는 경로 중 최소 간선값의 최댓값 리턴
return dist[f2]
print(max_dijkstra(f1))
