(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
뱀 JOI는 어느 큰 저택에서 길을 잃었다. 저택에 사는 사람들에게 들키기 전에 저택을 탈출해야 한다.
저택에는 1호실부터 N호실까지 N개의 방과 M개의 복도가 있으며, 1 ≤ i ≤ M에 대해 i번 복도는 Ai호실과 Bi호실을 연결한다. 복도는 양방향으로 지나갈 수 있으며, i번 복도를 통과하는 데는 Di분이 걸린다. 복도 이외에 방 사이를 오갈 수 있는 방법은 없다.
저택의 각 방은 온도가 일정하게 조절되어 있으며, JOI에게는 너무 춥거나, 적당하거나, 너무 더울 수 있다. JOI는 급격한 온도 변화에 대응하지 못하기 떄문에, 마지막으로 너무 추운 방에서 나온 뒤 X분이 지나기 전에 너무 더운 방으로 들어가거나, 너무 더운 방에서 나온 뒤 X분이 지나기 전에 너무 추운 방으로 들어갈 수 없다.
JOI는 방에 도착하면 즉시 그 방을 빠져나가야 한다. 또한, 복도를 지나가는 중 되돌아가거나 i번 복도를 통과하는 데 Di분보다 많은 시간을 쓸 수도 없다. 이미 방문한 방에 다시 들어가거나 지나간 복도를 다시 지나가는 것은 가능하다.
JOI는 현재 1호실에 있고, 이 방은 JOI에게 너무 춥다. JOI가 저택에서 탈출하려면 출구가 있는 N호실로 이동해야 한다. JOI가 저택에서 탈출하는 데 걸리는 최단 시간을 구하여라.
입력
첫째 줄에 저택의 방 개수 N, 복도 개수 M, JOI가 온도 변화에 대응하는 시간 X가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 10,000, 1 ≤ M ≤ 20,000, 1 ≤ X ≤ 200)
다음 N줄에 걸쳐 각 방의 온도가 주어진다. 이 중 i번째 줄에는 정수 Ti (0 ≤ Ti ≤ 2)가 주어지며, Ti = 0이면 i호실이 너무 추운 경우, Ti = 1이면 적당한 경우, Ti = 2이면 너무 더운 경우이다. T1 = 0이다.
다음 M줄에 걸쳐 복도의 정보가 주어진다. 이 중 j번째 줄에는 j번 복도에 연결되어 있는 두 방 Aj, Bj와 j번 복도를 통과하는 시간 Dj가 공백으로 구분되어 주어진다. (1 ≤ Aj < Bj ≤ N, 1 ≤ Dj ≤ 200) 같은 방의 쌍을 연결하는 복도가 여러 개 있을 수 있다.
JOI가 저택에서 탈출할 수 있는 경우만 입력으로 주어진다.
출력
JOI가 저택에서 탈출하는 데 걸리는 최단 시간을 한 줄로 출력한다.
힌트
예제 입력 1에서는 1-2-3-4-5-6-5-8 순서로 이동하는 것이 최적이다.
예제 입력 2에서는 같은 방의 쌍(eg. 1호실과 5호실)을 연결하는 복도가 여러 개 주어진다.
dlaud5379 1년 전 1
(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
뱀 JOI는 어느 큰 저택에서 길을 잃었다. 저택에 사는 사람들에게 들키기 전에 저택을 탈출해야 한다.
저택에는 1호실부터 N호실까지 N개의 방과 M개의 복도가 있으며, 1 ≤ i ≤ M에 대해 i번 복도는 Ai호실과 Bi호실을 연결한다. 복도는 양방향으로 지나갈 수 있으며, i번 복도를 통과하는 데는 Di분이 걸린다. 복도 이외에 방 사이를 오갈 수 있는 방법은 없다.
저택의 각 방은 온도가 일정하게 조절되어 있으며, JOI에게는 너무 춥거나, 적당하거나, 너무 더울 수 있다. JOI는 급격한 온도 변화에 대응하지 못하기 떄문에, 마지막으로 너무 추운 방에서 나온 뒤 X분이 지나기 전에 너무 더운 방으로 들어가거나, 너무 더운 방에서 나온 뒤 X분이 지나기 전에 너무 추운 방으로 들어갈 수 없다.
JOI는 방에 도착하면 즉시 그 방을 빠져나가야 한다. 또한, 복도를 지나가는 중 되돌아가거나 i번 복도를 통과하는 데 Di분보다 많은 시간을 쓸 수도 없다. 이미 방문한 방에 다시 들어가거나 지나간 복도를 다시 지나가는 것은 가능하다.
JOI는 현재 1호실에 있고, 이 방은 JOI에게 너무 춥다. JOI가 저택에서 탈출하려면 출구가 있는 N호실로 이동해야 한다. JOI가 저택에서 탈출하는 데 걸리는 최단 시간을 구하여라.
입력
첫째 줄에 저택의 방 개수 N, 복도 개수 M, JOI가 온도 변화에 대응하는 시간 X가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 10,000, 1 ≤ M ≤ 20,000, 1 ≤ X ≤ 200)
다음 N줄에 걸쳐 각 방의 온도가 주어진다. 이 중 i번째 줄에는 정수 Ti (0 ≤ Ti ≤ 2)가 주어지며, Ti = 0이면 i호실이 너무 추운 경우, Ti = 1이면 적당한 경우, Ti = 2이면 너무 더운 경우이다. T1 = 0이다.
다음 M줄에 걸쳐 복도의 정보가 주어진다. 이 중 j번째 줄에는 j번 복도에 연결되어 있는 두 방 Aj, Bj와 j번 복도를 통과하는 시간 Dj가 공백으로 구분되어 주어진다. (1 ≤ Aj < Bj ≤ N, 1 ≤ Dj ≤ 200) 같은 방의 쌍을 연결하는 복도가 여러 개 있을 수 있다.
JOI가 저택에서 탈출할 수 있는 경우만 입력으로 주어진다.
출력
JOI가 저택에서 탈출하는 데 걸리는 최단 시간을 한 줄로 출력한다.
힌트
예제 입력 1에서는 1-2-3-4-5-6-5-8 순서로 이동하는 것이 최적이다.
예제 입력 2에서는 같은 방의 쌍(eg. 1호실과 5호실)을 연결하는 복도가 여러 개 주어진다.