파일 업로드

우유 생산 파이프

profile
실행 시간 제한메모리 제한
1 초512 MB
📃 해결할 문제

수현은 최근에 새로운 공장을 구입하여 그의 우유 생산 인프라를 확대했습니다. 새 공장은 인근 마을에 파이프 네트워크를 통해 연결되어 있으며, 수현은 공장에서 마을로 우유를 펌핑하기 위해 사용할 파이프 중 가장 좋은 세트를 고르는 방법을 알아내려고 합니다.

파이프 네트워크는 NN 개의 접점들 (파이프의 끝점들), 편리하게도 1N1 \ldots N 까지 번호가 매겨져 있습니다. (2N10002 \leq N \leq 1000). 접점 1은 수현의 공장을 표시하며, 접점 NN 은 마을입니다. 두 접점들을 연결하는 MM 개의 양방향 파이프가 있습니다.(1M10001 \leq M \leq 1000) ii 번째 파이프는 수현이 사용하기 위해 구입하는데 cic_i 달러가 들고, fif_i 리터의 우유를 초당 흐르게 할 수 있습니다.

수현은 접점 1과 NN 이 끝점인 한 개의 경로만 파이프를 구입하려고 합니다. 경로의 비용은 경로를 따라가는 파이프의 비용의 합입니다. 경로를 따라 가는 흐름의 속도는 경로를 따라 가는 파이프 중 가장 작은 흐름의 속도입니다. (이것은 경로를 따라가는 흐름의 병목 현상입니다). 수현은 흐름속도를 경로의 비용으로 나눈 값을 최대화하려고 합니다. 11 부터 NN 까지의 경로가 존재함이 보장됩니다.

💻 입력

입력의 첫 번째 줄에는 NNMM 이 주어집니다. 이어지는 MM 줄 각각은 네 개의 정수로 파이프를 설명합니다: aabb (파이프로 연결된 두 접점), cc (비용), ff (흐름속도). 비용과 흐름속도는 모두 110001 \ldots 1000 범위의 양의 정수입니다.

🖨️ 출력
최적해 값에 10610^6 을 곱한 후 정수 형태로 (즉, 이 수가 정수 자체가 아닌 경우 다음으로 가장 낮은 정수로 내림) 출력해 주세요.

💻 예제 입력 1
3 2
2 1 2 4
2 3 5 3
🖨️ 예제 출력 1
428571

💡 힌트

이 예제에서는 11 에서 NN 까지의 경로는 하나뿐입니다. 그 흐름은 min(3,4)=3min(3,4) = 3 이고 그 비용은 2+5=72+5=7.


출처: USACO 2019 December Contest, Gold Problem 1. Milk Pumping