최소 비용으로 물건 보내기
레벨 MC · 코딩 · JavaScript · 목표 시간 45분 · 게시일 2026-11-04
0번부터 n-1번까지의 창고와 일방통행 운송로 pipes([출발, 도착, 용량, 단가])가 주어진다. 운송로 하나로는 최대 용량개까지 보낼 수 있고, 한 개를 보낼 때마다 단가만큼 비용이 든다. 물건은 창고에서 나뉘거나 합쳐져도 된다. 0번 창고에서 n-1번 창고로 물건을 정확히 need개 보내는 데 드는 비용의 최솟값을 구하시오. 그만큼 보낼 수 없으면 -1이다.
n은 2 이상 100 이하, 운송로는 최대 1,000개, 용량은 1 이상 20 이하, 단가는 0 이상 100 이하, need는 1 이상 1,000 이하이다. 매번 가장 싼 길로 보내기만 하면 답이 틀릴 수 있다.
예제
solve(4, [[0,1,2,1],[0,2,1,5],[1,2,1,1],[1,3,1,6],[2,3,2,1]], 3) solve(3, [[0,1,5,1],[1,2,2,1]], 3) solve(2, [[0,1,3,7],[0,1,1,2]], 2)