문제
운송회사는 종종 한 도시에서 다른 한 도시로 물품을 운반하는 경우가 있다.
운송회사는 물품 배송이 계약된 호텔들을 특별하게 대우하는데 그 이유는 운송기사가 계약된 호텔에서는 무료로 잠을 자고 쉴 수 있기 때문이다. 운송기사는 안전을 위하여 하루에 10시간만 운전할 수 있다.
운송회사는 경비 절감을 위하여 운전기사가 밤을 모낼 때는 계약된 호텔에서만 지내면서 출발 도시로부터 목적도시로 물품을 배송하기를 원한다. 또한 물품의 배송 날수가 가능한 적게 걸리게 하면서 배송기사가 머물게 되는 호텔의 수도 적게 하고자 한다.
입력
첫 행에 도시의 수 N ( 2 ≤ N ≤ 10,000)이 입력된다. 도시의 번호는 편의 상 1부터 N까지로 하며 1은 출발도시 N은 목적도시이다.
두 번째 행에 계약된 호텔의 수 H ( 0 ≤ H ≤ 100)와 H개의 호텔이 있는 도시의 번호가 공백으로 구분하여 입력된다.
세 번째 행에 도시 간 길의 수 M ( 1 ≤ M ≤ 100,000)이 입력된다.
네 번째 행에서부터 M개의 행에 걸쳐 길의 정보 s, e ( 1 ≤ s, e ≤ N), t ( 1 ≤ t ≤ 600)가 공백으로 구분되어 주어진다.
t 는 두 도시 s, e 사이를 이동하는 데 걸리는 시간으로 단위는 분이다.
<제약조건> • 서브태스크 1~2 : 2≤n≤20, 0≤H≤10. 1≤M≤60 • 서브태스크 3~4 : 2≤n≤60, 0≤H≤60. 1≤M≤1000 • 서브태스크 5~7 : 0≤H≤100 • 서브태스크 8~9 : 별도의 조건 없음
출력
1번 출발 도시로부터 N번 목적도시까지 물품을 배송하는데 가능한 적은 날 수를 소요하면서 머물게 되는 호텔의 최소수를 출력하시오. 운전기사는 하루에 10시간만 운전이 가능하며 계약된 호텔에서만 잠을 자야 한다.
만약 가능한 경우가 없다면 –1을 출력한다.
예제
6
3 2 5 3
8
1 2 400
3 2 80
3 4 301
4 5 290
5 6 139
1 3 375
2 5 462
4 6 300
2
출처
Ulm 2009
로그인해야 코드를 작성할 수 있어요.