레이팅 미적용농부 존(Farmer John)의 농장에는 헛간에서 우유 저장 탱크로 우유를 퍼 올리는 M개 (1 <= M <= 500)의 낡은 파이프 네트워크가 있다. 존은 내년에 걸쳐 이들 대부분을 철거하고 교체하고 싶지만, 헛간에서 저장 탱크로 여전히 우유를 보낼 수 있도록 정확히 하나의 경로에 해당하는 파이프들은 그대로 남겨 두고 싶어 한다.
파이프 네트워크는 N개 (1 <= N <= 500)의 연결 지점으로 표현되며, 각 연결 지점은 여러 파이프의 끝점이 될 수 있다. 연결 지점 1은 헛간이고, 연결 지점 N은 저장 탱크이다. M개의 양방향 파이프 각각은 두 연결 지점 사이를 잇고, 지연 시간(우유가 파이프의 한쪽 끝에서 다른 쪽 끝까지 도달하는 데 걸리는 시간)과 용량(정상 상태에서 파이프를 통해 단위 시간당 퍼 올릴 수 있는 우유의 양)을 가진다. 같은 연결 지점 쌍 사이에 여러 파이프가 연결될 수 있다.
헛간에서 탱크로 이어지는 파이프 경로에 대해, 경로의 지연 시간은 경로 위 파이프들의 지연 시간의 합이고, 경로의 용량은 경로 위 파이프들의 용량의 최솟값이다. FJ가 지연 시간 L, 용량 C인 파이프 경로로 총 X 단위의 우유를 보내려면, 걸리는 시간은 따라서 L + X/C이다.
FJ의 파이프 네트워크 구조가 주어질 때, X 단위의 우유를 최소 총시간에 퍼 올릴 수 있는, 헛간에서 저장 탱크로 가는 단일 경로를 고르는 것을 도와주자.
첫째 줄: 공백으로 구분된 세 정수 N M X (1 <= X <= 1,000,000).
둘째 줄부터 1+M번째 줄까지: 각 줄은 네 정수 I J L C로 파이프 하나를 설명한다. I와 J (1 <= I,J <= N)는 파이프 양 끝의 연결 지점이다. L과 C (1 <= L,C <= 1,000,000)는 파이프의 지연 시간과 용량이다.
FJ가 단일 경로로 우유를 보내는 데 걸리는 최소 시간을 정수로 내림한 값.
mroute.in · 출력을 쓸 파일 mroute.out3 3 15
1 2 10 3
3 2 10 2
1 3 14 127Output details: The path 1->2->3 takes 20 + 15/2 = 27.5 units of time, rounded down to 27, and is optimal.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > December > Silver