시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 38 17 6 33.333%

문제

계속 앉아서 열심히 공부(?)만 하는 학생들은 운동량이 절대적으로 부족하다. 우리의 원장선생님은 이런 학생들을 불쌍히 여기시어 운동을 할 계획을 세우셨다. 그 운동은 바로 단체 릴레이 경주이다. 릴레이 경주란 다들 알다시피 1개의 baton을 가지고 서로 baton을 전달해 주며 달리는 경기이다.

N(N<=1,000,000)명의 학생들은 운동장으로 나와서 T(2<=T<=100)개의 구역에서 바톤을 받을 준비를 하고 있다. 구역과 구역사이는 무조건 1개의 길만 존재한다. 쉽게 말해서 그래프의 구조를 가지고 있다.

릴레이를 하기 위해 각각의 학생들은 구역에 서 있으며 어떤 구역에는 여러명의 사람들이 있을 수 있다. 또한 릴레이의 특성상 baton이 하나기 때문에 각 구역으로 이동하는 데는 1명만 이동할 수 있으며 1명의 학생은 1개의 구간만 달린다. 그래서 학생들은 구역에 적당이 서서 바톤을 받아 끝나는 지점 까지 도달하여야 한다. 그런데 학생들은 운동을 오래 하고 싶지 않아 한다. 그렇기 때문에 시작지점에서 끝나는 지점까지의 최단경로를 알고 싶어 한다. 학생들이 어느 구역에 배치 되어야 되는지 프로그램을 짜서 도와주자. 시작 지점에서 끝지점 까지 정확히 길이(거치는 간선의 수)가 N이 되는 최단경로의 길이를 구하자.

  • N명의 학생은 모두 달려야 한다.
  • 시작점이나 도착지점에서 학생들이 바톤을 기다릴 수는 있지만 끝날 때에는 마지막 학생이 도착구역으로 가야 한다.
  • 물론 사용한 길을 다시 갈 수도 있다.

입력

첫째 줄에 학생의 수 N(N<=1,000,000)과 구역의 수(T<=100) 시작지점의 번호S(1<=S<=1000) 도착지점의 번호 E(1<=E<=1000)가 주어진다. 그 다음 T개의 줄에 간선의 길이 L (1 ≤ L ≤ 1,000)과 간선을 잇는 두 점이 순서대로 주어진다. 참고로 번호는 1 2 3 4 순서대로 들어오지 않는다.

출력

첫째 줄에 최단경로의 길이를 구하라. 제한시간은 1초이다.

예제 입력

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

예제 출력

10

힌트

시작 지점이 6번과 8번에 학생이 서 기다리고 있으면 최단경로가 10이 된다. 6-9-8-4의 경로가 있지만 학생수가 2명 이기 때문에 우리가 원하는 경로가 아니다

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO November 2007 Contest > Gold 2번