1939번: 중량제한 - 최단 경로(다익스트라)
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 관찰, 알고리즘 시작점에서 도착점까지의 최대 중량 제한을 구하기 위해서는, 그 전에 시작점에서 도착점 바로 이전의 정점까지의 최대 중량 제한을 구할 필요가 있다. 도착점 바로 이전 정점에서 도착점까지의 최대 중량 제한은 간선의 그 가중치 자체이기에 고정된 값이기 때문이다. 그런데 이와 같은 논리는 다익스트라 알고리즘의 정당화 증명과 같다...
알고리즘/baekjoon
2023. 5. 7. 14:21
