algospot 여행 경로 정하기 (문제 ID: TPATH) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/TPATH

algospot.com :: TPATH

각 도시들을 잇는 철도망이 주어질 때, 0번 도시에서 출발해서 V-1번 도시에 도착하는 경로들 중 최대 운행 속도와 최소 운행 속도의 차를 최소화하는 경로를 찾는 문제이다.

 

0번 도시와 V-1번 도시가 연결될 때까지 하한을 높여가며 다음과 같은 동작을 반복한다.

하한을 두고 kruscal알고리즘을 이용하여 하한이상의 가중치를 가진 철도부터 가중치 순서대로 그래프에 추가한다.

이때 kruscal의 시간복잡도를 지배하는 것은 edges를 가중치의 오름차순으로 정렬하는 작업이다.

문제에서 철도의 가중치가 변하지는 않으므로 edges를 정렬하는 작업을 선행처리한 후 나머지 부분만 하한을 높여가며

반복하면 기존의 kruscal알고리즘을 edges.size번 반복하는 것보다 빠르게 문제를 해결 할 수 있다.

 

 

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/31.%20MST/TPATH.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2