Problemas
정올 자동차 회사에서는 최근 슈퍼 카 J7을 개발했다. J7의 성능 테스트를 위하여 성능 시험장의 도로를 주행할 예정이다. 성능 시험장은 여러 개의 교차로가 있으며 이들 교차로와 연결된 도로들이 있다. 성능 시험장의 모든 도로의 길이는 1㎞로 일정하지만 도로를 이용하는 비용은 서로 다를 수 있다. 또한 임의의 두 교차로를 직접 연결하는 도로는 한 개 뿐이고 양방향으로 통행할 수 있다.
정올 자동차 회사는 이들 도로 중에 R( 1≤R≤128)개의 연결된 도로를 선택하여 D(1＜D＜1,048,576 )㎞를 달릴 예정이다. 편의상 교차로에 번호를 붙여 표시하고 선택한 도로에 대한 정보는 교차로 번호로 나타내기로 한다. 정올 자동차 회사는 시작교차로 번호 S로부터 종료 교차로 번호 E (1≤S, E≤100,000) 까지 D㎞ 를 주행하는데 드는 비용을 최소화 하고자 한다. 선택한 도로 중에 같은 도로를 여러 번 주행할 수도 있고 어떤 도로는 한 번도 주행하지 않을 수도 있다. 선택된 도로들을 연결하는 교차로는 적어도 2개 이상의 도로를 연결한다.
예를 들어 주행하고자 거는 거리가 7㎞ 이고 선택한 도로의 개수가 8개, 시작 교차로 번호가 10, 종료 교차로 번호가 33 이라고 하자. 그리고 선택한 8개 도로의 정보가 아래 그림과 같다고 하자.원 안의 번호는 교차로 번호이고 간선은 도로이며 간선 옆의 숫자는 통행 비용이다.
이 경우 교차로 번호 10 -> 1 -> 25 -> 1 -> 25 -> 1 -> 25 -> 33 로 주행하는 것이 비용 10으로 최소 이다.
Entrada
첫 행에 주행하고자 하는 거리 D와 선택한 도로의 개수 R 이 입력된다. 두 번째 행에 시작교차로 번호 S와 종료교차로 번호 E가 입력된다. 세 번째 행에서부터 R개의 행에 걸쳐 교차로 번호 Ki1과 Ki2(1≤Ki1, Ki2≤100,000), 그리고 그 비용 Ci( 1≤Ci≤1,024)가 입력된다.
Salida
시작교차로 S로부터 종료교차로 E까지 D㎞를 주행하는데 필요한 최소비용을 출력한다.
Ejemplo
7 8
10 33
25 1 1
1 10 2
10 99 1
33 1 8
99 1 5
10 33 6
25 33 3
99 33 4
10
Debes iniciar sesión para escribir código.