고속도로
시간 제한2초메모리 제한128 MB
길이와 통행료가 있는 방향 그래프에서, 총 통행료가 예산 K를 넘지 않는 조건으로 도시 1에서 N까지 가는 최단 경로 길이를 구합니다.
문제
봄캠프가 열리는 동안 고속도로 통행료가 크게 올랐다. 참가자들은 통행료가 오르기 전에 계산해 온 교통비만 가지고 집으로 돌아가야 하므로, 예산을 넘기면 속초에 더 머물러야 할지도 모른다.
도시는 번호가 붙은 정점이고, 도로는 한 도시에서 다른 도시로만 이동할 수 있는 일방통행 간선이다. 각 도로에는 길이와 통행료가 있다. 속초는 1번 도시이고, 집은 N번 도시이다.
준비한 교통비 K를 넘지 않으면서 1번 도시에서 N번 도시까지 갈 수 있다면, 가능한 경로 중 총 길이가 가장 짧은 값을 구하라. 갈 수 없다면 -1을 출력한다.
입력
첫째 줄에 준비한 교통비 K가 주어진다. (0 <= K <= 10,000)
둘째 줄에 도시의 수 N이 주어진다. (2 <= N <= 100)
셋째 줄에 도로의 수 R이 주어진다. (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을 출력한다.