의약품 수송

면접 대비

시간 제한1초메모리 제한1024 MB

요약
한 정착지에서 다른 정착지로 가는 가장 빠른 길을 찾습니다. 주행 100분을 넘기기 전에 대피소에서 5분 세차하며 이동합니다.
난이도

보통10점 중 6점

유형
최단 경로, 그래프, 힙, 동적 계획법
정답자
아직 제출이 없습니다

문제

표면 대부분이 사막인 미개척 행성에 두 탐사대가 파견되어 개척지를 세웠다. 이 사막은 매우 황량하고 모래 바람이 세차게 불어서, 탐사 차량으로 이동하려면 포장된 도로만 이용해야 하고 중간중간 특수 장비로 모래를 씻어 주어야 한다. 그렇게 하지 않으면 차량에 모래가 많이 묻어 주행 불능 상태가 된다. 모래를 씻는 데는 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로) 가는 데 걸리는 시간을 분 단위로 나타낸 값이다.

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

출력

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

예제3

  1. 예제 1

    입력
    1 3
0 1 40
1 2 80
0 2 110
    예상 출력
    125

  2. 예제 2

    입력
    0 1
0 1 100
    예상 출력
    100

  3. 예제 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
    예상 출력
    310