Informatica Online Judge

  선체의 두께 [2176 / 0880]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 6   Total Tried : 10


The Champion of this Problem (C++) : icp1481 - 0ms / 1092byte
My Best Submission (C++) : N/A

[CCC2015S4]

Background

섬이 많은 다도해를 배를 타고 여행 중이고, 타고 있는 배는 $K$ 센티미터의 선체 두께를 가지고 있다.

다도해에는 $1$ 부터 $N$ 까지 번호가 붙여진 섬 $N$ 개가 있고, 그 섬들 사이를 이동할 수 있는 $M$개의 해로 노선이 있다. $i$번 노선은 $a_i$ 번 섬과 $b_i$ 번 섬 사이를 연결하는 직선 경로인데, 이동 시간은 $t_i$ 분 걸리고 섬 사이의 암초들 사이를 지나가면 $h_i$ 센티미터만큼 선체를 깎아 마모시킨다.

섬들 사이의 노선들을 이용해서, 선체를 모두 파손시키지 않으면서 어떤 섬 $A$에서 다른 섬 $B$로 여행하려고 하고 있다. - 각 노선들을 이동할 때 파손되는 선체 두께 $h_i$ 의 합이 배의 선체 두께인 $K$ 보다 작아야 한다.

또한, 여행 일정이 빠듯하기 때문에 $A$ 섬에서 $B$ 섬으로 최대한 빠른 시간 내에 이동해야한다. 하지만, 이동할 수 있는 노선을 만들 수 없는 경우도 있을 수 있고 배의 선체 두께가 충분히 튼튼하지 못할 수도 있다.

Input

첫 번째 줄에는 $K$, $N$, $M$ 가 공백을 두고 입력된다.

두 번째 줄부터 $M$ 개의 줄에는 $a_i$, $b_i$, $t_i$, $h_i$ 가 공백을 두고 한 줄씩 입력된다.

($i$번째 줄에는 $a_i$ 섬에서 $b_i$ 섬으로 이동하는 노선의 이동시간 $t_i$ 와 그 때 마모되는 선체의 두께 $h_i$ 가 입력되는 것이다.)

$a_i$ 와 $b_i$ 는 서로 다르다.

마지막 번째 줄에는 이동을 시작하는 섬의 번호 $A$ 와 이동하려는 섬의 번호 $B$ 가 공백을 두고 입력된다.

[입력값의 정의역]
$1≤K≤200$
$2≤N≤2000$
$1≤M≤10,000$
$1≤t_i≤10^5$
$0≤h_i≤200$
$1≤a_i,b_i≤N$
$1≤A,B≤N$
$A≠B$

Output

선체를 모두 파손시키지 않으면서, $A$ 섬에서 $B$ 섬으로 이동하는데 필요한 최소 시간을 출력한다. 가능한 방법이 없다면 $–1$을 출력한다.

IO Example

입력 예시1
10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4

출력 예시1
7

*설명 : 1->4 로 바로 이동하는 경로는 선체를 모두 파손 시킨다. 1->2->4 로 이동하거나, 1->3->4 로 이동하는 방법은 최소 8분 걸린다. 1->2->3->4 7분이 걸리고 선체를 7 만큼 마모시킨다. 1->3->2->4 는 13분 걸리지만 선체는 5 만큼만 마모된다.


입력 예시2
3 3 3
1 2 5 1
3 2 8 2
1 3 1 3
1 3

출력 예시2
-1

*설명 : 1->3 방법이나 1->2->3 방법도 모두 선체 두께를 0으로 만든다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]