우유 배송 경로

면접 대비

시간 제한1초메모리 제한128 MB

요약

1번 노드에서 N번 노드까지 가는 경로 중 지연 시간 합과 X를 경로의 최소 용량으로 나눈 값을 더한 시간이 최소가 되는 경로를 골라 내림한 값을 구한다.

난이도: 보통10점 중 5점
유형: 그래프, 최단 경로, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

농부 존의 농장에는 외양간에서 우유 저장 탱크로 우유를 보내기 위한 낡은 파이프 네트워크가 있으며, 파이프는 총 $M$ 개 ( $1 \le M \le 500$ )입니다. 그는 내년에 대부분의 파이프를 교체하려 하지만, 외양간에서 저장 탱크까지 우유를 계속 보낼 수 있도록 정확히 하나의 경로에 해당하는 파이프만 그대로 남겨 두려고 합니다.

파이프 네트워크는 $N$ 개의 분기점 ( $1 \le N \le 500$ )으로 이루어져 있으며, 각 분기점은 여러 파이프의 끝점이 될 수 있습니다. 분기점 $1$ 은 외양간이고, 분기점 $N$ 은 저장 탱크입니다. $M$ 개의 파이프는 각각 두 분기점을 잇는 양방향 파이프이며, 지연 시간(우유가 파이프의 한쪽 끝에서 반대쪽 끝까지 도달하는 데 걸리는 시간)과 용량(정상 상태에서 단위 시간당 통과시킬 수 있는 우유의 양)을 가집니다. 같은 두 분기점을 잇는 파이프가 여러 개 존재할 수도 있습니다.

외양간에서 탱크로 이어지는 파이프 경로에 대해, 경로의 지연 시간은 그 경로에 포함된 파이프들의 지연 시간의 합이고, 경로의 용량은 그 경로에 포함된 파이프들의 용량 중 최솟값입니다(이 최소 용량이 전체 배송 속도를 제한하는 '병목'이기 때문입니다). 지연 시간이 $L$ 이고 용량이 $C$ 인 경로로 총 $X$ 단위의 우유를 보내는 데 걸리는 시간은 $L + X/C$ 입니다.

주어진 파이프 네트워크에서 $X$ 단위의 우유를 최소 시간에 보낼 수 있는, 외양간에서 저장 탱크까지의 단일 경로 하나를 선택했을 때의 최소 시간을 구하세요.

입력

첫째 줄: 공백으로 구분된 세 정수 $N$ , $M$ , $X$ ( $1 \le X \le 1{,}000{,}000$ ).
둘째 줄부터 $M$ 개의 줄: 각 줄은 하나의 파이프를 네 정수 $I$ , $J$ , $L$ , $C$ 로 나타냅니다. $I$ 와 $J$ ( $1 \le I, J \le N$ )는 파이프 양 끝의 분기점이고, $L$ 과 $C$ ( $1 \le L, C \le 1{,}000{,}000$ )는 각각 그 파이프의 지연 시간과 용량입니다.

출력

첫째 줄: 하나의 경로로 우유를 보내는 데 걸리는 최소 시간을 소수점 이하를 버려 정수로 출력합니다.

힌트

$X = 15$ 단위의 우유를 보낸다고 합시다. 분기점 $1$ (외양간)과 분기점 $3$ (탱크)을 직접 잇는 지연 시간 $14$ , 용량 $1$ 짜리 파이프만 사용하면 $14 + 15/1 = 29$ 가 걸립니다. 반면 $1 \to 2 \to 3$ 경로는 지연 시간이 $10 + 10 = 20$ , 용량이 $\min(3, 2) = 2$ 이므로 $20 + 15/2 = 27.5$ 가 걸려 더 유리합니다. 소수점 이하를 버리면 답은 $27$ 입니다.

예제3

예제 1
입력
```
3 3 15
1 2 10 3
3 2 10 2
1 3 14 1
```
예상 출력
```
27
```
예제 2
입력
```
2 1 100
1 2 5 10
```
예상 출력
```
15
```
예제 3
입력
```
2 2 10
1 2 1 1
1 2 5 5
```
예상 출력
```
7
```