시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 14 14 14 100.000%

문제

표면 대부분을 사막이 차지하는 미개척 행성에 두 탐사대가 파견되어 개척지를 세웠다. 이 사막은 매우 황량하여 모래 바람이 세차게 불기 때문에 탐사 차량으로 이동하기 위해선 포장된 도로만을 이용해야 하고 특수 장비를 이용해 중간중간 모래를 씻어주어야 한다. 그렇지 않으면 차량에 모래가 많이 묻어 주행 불능 상태에 빠지게 된다. 모래를 씻는 데에는 5분이 걸리고, 모래를 씻은 후에는 최대 100분간 씻지 않고 주행할 수 있다. 특수 장비는 사막 곳곳에 배치되어 있으며 그 개수는 총 N개이고 관리를 위해 1부터 N까지 차례대로 관리 번호가 붙어 있다. 포장 도로는 개척지 또는 특수 장비가 있는 위치 사이를 연결한다. 두 포장 도로가 양 끝점이 아닌 곳에서 만나는 일은 없다.

탐사가 진행되는 도중 한 개척지에서 환자가 발생하여 다른 개척지로부터 의약품을 수송받으려 한다. 탐사 차량으로 의약품을 수송하는 데 걸리는 최소 시간을 구하여라.

입력

첫째 줄에는 특수 장비의 개수 N과 포장 도로의 개수 K가 공백으로 구분되어 입력된다. (0 ≤ N ≤ 1000; 1 ≤ K ≤ 3000)

둘째 줄부터 K+1째 줄에는 각 줄마다 정수 u, v, t가 공백으로 구분되어 입력된다. (0 ≤ u, v ≤ N+1; 1 ≤ t ≤ 1000)

u와 v는 도로의 양 끝점으로, 특수 장비의 관리 번호를 의미한다. 단, 번호가 0이면 의약품을 보내는 개척지, N+1이면 받는 개척지이다. t는 u에서 v로 (또는 v에서 u로) 가는 데 걸리는 시간을 분 단위로 나타낸 것이다.

항상 두 개척지 사이를 차량으로 오갈 수 있는 경우만 주어진다. 출발 직전, 차량에 묻은 모래는 모두 씻은 상태이다.

출력

탐사 차량이 의약품을 수송하는 데 걸리는 최소 시간을 분 단위로 출력한다.

예제 입력 1

1 3
0 1 40
1 2 80
0 2 110

예제 출력 1

125

0에서 2로 바로 가는 길은 110분이 걸려 가다가 차량이 고장나게 되므로 갈 수 없다. 0에서 1을 거쳐 2로 가되 1에서 5분간 모래를 씻어주면 된다.

예제 입력 2

0 1
0 1 100

예제 출력 2

100

특수 장비가 하나도 없지만 아슬아슬하게 도착할 수 있다.

예제 입력 3

6 8
0 1 59
1 2 59
2 3 59
3 4 59
4 7 59
0 5 100
5 6 100
6 7 100

예제 출력 3

310

0에서 1 2 3 4를 거쳐 7로 가면 59분이 걸리는 길을 5개 지나고, 총 4번을 쉬게 되어 315분이 걸린다. 반면에 0에서 5 6을 거쳐 7로 가면 100분이 걸리는 길을 3개 지나고 2번 쉬게 되어 310분밖에 걸리지 않는다.

출처

Contest > 웰노운컵 > 제2회 웰노운컵 Day 2 D번