용감한 공주 다시 보기
시간 제한8초메모리 제한512 MB
가중 무방향 그래프와 예산 L이 주어질 때, 1번 노드에서 N번 노드까지 이동하는 경로 중 경비 비용의 합이 예산을 넘지 않으면서 조우하는 적의 수를 최소화하는 경로를 찾는다.
문제
가난한 나라의 말괄량이 용감한 공주가 정략 결혼을 위해 다른 나라로 시집을 가게 되었다. 그런데 공주를 죽이려는 악당이 시집가는 길 도중에 자객을 풀어 놓았다.
공주를 무사히 상대국에 보내기 위해 너는 이미 안전한 경로를 정해 두었지만, 공주가 지금까지 지나간 적 없는 길로 가 보고 싶다는 제멋대로인 간절한 부탁 때문에 다른 길로 가게 되었다. 그래서 너는 지도를 보면서 공주가 지날 길을 다시 정하기로 했다.
모든 길은 숙소와 숙소를 잇는 가도이다. 편의상 출발 지점과 목적 지점도 숙소로 둔다. 그런데 새로 정한 길은 치안에 문제가 있었다. 도적이나 공주를 죽이려는 자객이 습격해 올 가능성이 높다.
그런 위험한 길을 지나려면 호위를 고용하는 것이 바람직하다. 호위는 숙소에서 고용할 수 있고, 길 단위로 공주를 지키게 할 수 있다. 호위가 지키는 동안에는 도적이나 자객에게 습격당하지 않지만, 거리 1마다 금 1이 든다. 따라서 호위를 고용하려면 소지금이 다음 숙소까지의 거리보다 적지 않아야 한다.
이제 주어진 예산 L 아래에서, 공주가 무사히 목적지에 도착할 때까지 습격해 오는 도적과 자객의 수를 최소화하려고 한다. 너의 일은 그 최소화된 수를 구하는 것이다. 숙소에 있는 동안에는 습격당하지 않는다.
입력
입력은 여러 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식이다.
N M L
A1 B1 D1 E1
A2 B2 D2 E2
...
AN BN DN EN
첫 줄에는 음이 아닌 정수 세 개 N (2 ≤ N ≤ 100), M, L (0 ≤ L ≤ 100)이 주어진다. 이 정수는 숙소의 수, 길의 수, 호위를 고용하기 위한 예산을 나타낸다. 숙소에는 1부터 N까지 번호가 붙어 있고, 출발지에는 1, 목적지에는 N이 붙어 있다.
이어지는 M개 줄에는 길의 정보가 한 줄에 하나씩 주어진다. 길의 정보는 정수 네 개 A**i, B**i (1 ≤ A**i < B**i ≤ N), D**i (1 ≤ D**i ≤ 100), E**i (0 ≤ E**i ≤ 10000)로 주어진다. 이는 각각 길의 시작 숙소와 끝 숙소의 번호, 길의 거리, 도적이나 자객에게 습격당하는 사람 수를 나타낸다.
길은 양방향으로 지날 수 있고, 한 숙소 쌍에 대해서는 길이 많아야 하나만 존재한다. 또한 출발지에서 목적지로는 반드시 이동할 수 있다.
입력의 끝은 공백으로 구분된 0 세 개를 포함하는 한 줄로 나타낸다.
출력
각 데이터셋에 대해 도적이나 자객에게 습격당하는 사람 수의 최솟값을 한 줄에 하나씩 출력한다. 출력에 불필요한 공백이나 줄바꿈을 넣어서는 안 된다.