시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 256 MB 1 0 (0%) 0
문제
당신은 흡혈귀이다. 그리고 당신은 어떤 지점 A에서 다른 지점 B로 여행하고 싶다. 당신은 지상에서 햇빛속에서 혹은 햇빛을 피하기 위해 지하의 터널을 통해 여행할 수 있다. 당신은 여행하고싶은 지점을 매핑해두었고, 몇몇 지점들 사이의 비밀 터널을 찾았고, 다른 지점들은 지상에서 걸어서 이동할 수 있다. 터널과 지상경로는 양방향이다. 당신은 총합 S초넘게 햇빛을 받으면 안되고(0 <= S <= 3600), 이 때 여행시간을 최소화 하고싶다. (당신은 초마다 1 단위거리를 움직인다)
입력
첫줄에 숫자 S, 햇빛을 받을 수 있는 최대 시간이 몇초인지 주어진다. 그 다음줄에 지점의 갯수 N (2 <= N <= 1600)과 지점을 연결하는 길의 수 E(1<=E<=10000)가 공백을 사이에 두고 주어진다. 그 다음 E개의 줄에는 각각 지점들 사이를 연결하는 길의 정보가 주어진다. 특히, 각각 줄은 네개의 숫자로 이루어져 있다: s (한쪽점) (0<=s<=N-1), t (반대쪽점) (0<=t<=N-1, s!=t), d(s와 t사이의 거리), u(지상의 길인지 지하의 터널인지에 대한 정보: 1인경우 지상이며, 0인경우 터널을 나타낸다) Note: 30%의 점수는 N<=50이라 가정해도 좋다.
출력
한개의 정수를 출력한다. 지점 0에서 지점 N-1로 갈 떼 최대 S시간만 햇빛을 받는 조건아래에서 최소 소요시간을 나타낸다. 만약 불가능하다면 -1을 출력한다.
힌트
입력예제 ``` 3 4 6 0 1 3 1 0 2 4 1 0 3 10 1 1 2 3 0 1 3 1 1 2 3 3 0 ``` 출력예제 ``` 9 ```