시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 992 | 316 | 213 | 30.647% |
봄캠프 기간 동안 고속도로의 통행료가 급격하게 올라, 참가자들이 자칫 집으로 돌아가지 못할 수도 있는 위기에 봉착했다! 통행료가 인하되기 전까지는 여기 속초에서 원쌤과 함께 계속 프로그래밍 공부를 해야 할 수도 있는 상황인 것이다! 이 모든 것은 귀가시에 사용할 교통비를, 고속도로 통행료가 오르기 전에 계산해서 들고 왔기 때문이다.
다급해진 여러분은 정해진 예산을 가지고 집으로 돌아갈 수 있을지 알아보고, 갈 수 있다면 그에 필요한 최단 이동거리를 계산하려고 한다. 이를 해결하기 위한 프로그램을 작성하라.
첫 줄에 여러분이 준비해 둔 교통비 K가 주어진다. (0≤K≤10,000) 둘째 줄과 셋째 줄에는 각각 도시의 숫자 N과 도로의 숫자 R이 주어진다. (2≤N≤100, 1≤R≤10,000) 이후 R개의 줄에 각 도로의 정보가 주어지는데, 각 줄은 네 개의 숫자 s, d, l, t로 이루어져 있다. s는 도로의 출발 도시 번호이고, d는 도로의 도착 도시 번호이다. l은 도로의 길이이고, t는 도로의 통행료이다. (1≤s≤N, 1≤d≤N, 1≤l≤100, 0≤t≤100)
도시의 번호는 1번부터 N번까지 빠짐없이 붙어 있다. 이곳 속초는 1번 도시이고, 여러분의 집은 N번 도시에 있다. 각 도로는 일방통행로이다. 서로 다른 두 도로가 서로 같은 시작 도시와 서로 같은 도착 도시를 가질 수 있음에 유의하라.
첫 줄에 정해진 예산 내에서 이용할 수 있는 경로 중 제일 짧은 것의 길이를 출력한다. 만약 가능한 경로가 없을 때에는 -1을 출력한다.
5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
11
0 4 4 1 4 5 2 1 2 1 0 2 3 1 1 3 4 1 0
-1
Olympiad > Central European Olympiad in Informatics > CEOI 1998 > Day 2 5번