글 읽기 - 지문이 완전히 깨져 있어요

index 2년 전 0

한자가 적힌 부분들이 전혀 관계 없는 다른 글자들로 바뀌어 있어서 문제를 제대로 읽을 수 없는 상황이에요.

srand 2년 전 0

jag-icpc 에서 문제를 다운로드 받은 후,

아래와 같은 명령어로 변환 후 chrome의 번역 기능 이용하시면 될 듯 싶습니다.

수정되기 전까지는 이렇게 이용하시면 될 듯 싶습니다.

iconv -f EUC-JP -t UTF-8 ./C.html > C.UTF-8.html

Brave Princess Revisited
용감한 공주 다시 나타난다.
English text is not available in this practice contest.

한 가난한 나라의 텐바에서 용감한 공주가 정약 결혼을 위해 다른 나라에 며느리가 되었다. 그런데 공주님을 죽은 자로 하려고 하는 악한이 며느리 앞으로 가는 길에 자객을 쏘고 있다.

공주님을 무사히 상대국에 배달하기 위해서, 당신은 안전한 경로를 이미 결정했지만, 공주님의 지금까지 다녔던 길을 지나 보고 싶다는 뜻 대로 남기라는 소원으로 다른 길을 지나갔다. 그래서 당신은 지도를 보면서 공주님이 지나가는 길을 다시 결정하기로 했습니다.

모든 길은 여관을 잇는 가도이다. 편의상, 출발지점 및 목적지점도 숙장으로 한다. 그런데 새로운 길은 치안의 문제를 안고 있었다. 도적이나 공주님을 죽은 자로 하려고 하는 자객이 덮쳐 올 가능성이 높다.

그러한 위험한 길을 통과하기 위해서는 호위를 고용하는 것이 바람직합니다. 호위는 숙소에서 고용할 수 있고 도로 단위로 공주를 지킬 수 있다. 호위가 지키고 있는 동안은 도적이나 자객에게 습격당하지 않지만, 거리 1당 금 1이 걸린다. 따라서 호위를 고용하기 위해서는 소지금보다 다음 숙소까지의 거리가 길지 않은 것이 조건이 된다.

이제 주어진 예산 L 하에서 공주가 무사히 목적지에 도착하기 전에 습격하는 도적과 자객의 인원수를 최소화하는 것을 생각한다. 당신의 임무는 최소화 된 인원수를 찾는 것입니다. 덧붙여 숙장에 있는 동안에 습격당하는 것은 아닌 것으로 한다.

입력
입력은 여러 데이터 세트로 구성됩니다. 각 데이터 세트는 다음 형식을 사용합니다.

N M L
A 1 B 1 D 1 E 1
A 2 B 2 D 2 E 2
...
A N B N D N E N
첫 번째 행에는 3 개의 음이 아닌 정수 N (2 ≤ N ≤ 100), M , L (0 ≤ L ≤ 100)이 주어집니다. 이 정수는 숙소의 수, 길의 수, 호위를 고용하기위한 예산을 나타냅니다. 숙소에는 1에서 N 까지의 번호가 할당되고, 출발지에는 1, 목적지에는 N 의 번호가 각각 할당되어 있다.

계속되는 M 행에서는 길의 정보가 각 행에 1개씩 주어진다. 길 정보는 4 개의 정수 A i , B i (1 ≤ A i < B i ≤ N), D i (1 ≤ D i ≤ 100) E i (0 ≤ E i ≤ 10000)로 주어진다. 이들은 각각 도로의 시작점과 종점의 숙소 번호, 도로의 거리, 도적과 자객에게 습격당하는 인원수를 나타낸다.

도로는 양방향으로 통행 할 수 있으며 한 곳에서 1 개의 길만 존재합니다. 또한 출발지에서 목적지로 반드시 이동할 수 있음을 보장합니다.

입력의 끝은 공백으로 구분 된 세 개의 0을 포함하는 한 줄로 표시됩니다.

Output
각 데이터 세트에 대해 도둑이나 자객에게 습격당하는 사람의 최소값을 각 행에 출력하십시오. 출력에 여분의 공백이나 개행을 포함해서는 안됩니다.

샘플 입력
3 2 10
1 2 8 6
2 3 10 3
3 2 10
1 2 3 8
2 3 7 7
3 3 10
1 3 17 6
1 2 2 4
2 3 9 13
4 4 5
1 3 9 3
1 4 7 25
2 3 8 2
2 4 9 3
0 0 0
Output for the Sample Input
3
0
4
8