반값 통행권 한 장
레벨 M6 · 코딩 · JavaScript · 목표 시간 27분 · 게시일 2026-10-30
0번부터 n-1번까지의 정점과 일방통행 도로 edges([출발, 도착, 통행료])가 주어진다. 반값 통행권이 한 장 있어서, 지나가는 도로 가운데 하나의 통행료를 절반(소수점 아래 버림)으로 낼 수 있다. 쓰지 않아도 된다. 0번에서 n-1번까지 가는 데 드는 통행료 합의 최솟값을 구하시오. 갈 수 없으면 -1이고, n = 1이면 0이다.
n은 최대 20,000, 도로는 최대 60,000개, 통행료는 1 이상 100,000 이하이다. 도로마다 통행권을 써 보며 매번 최단 경로를 새로 구하는 방법으로는 시간 안에 끝나지 않는다.
예제
solve(4, [[0,1,10],[1,3,10],[0,2,3],[2,3,30]]) solve(3, [[0,1,5],[2,1,1]]) solve(1, [])