kms1601   2년 전

문제

건물을 유치원으로 개조하기 위해 한 곳에서 다른 곳으로 많은 자재를 운송해야 합니다. 운송해야 할 자재에는 시멘트, 모래, 철근은 물론 의자, 창문, 컴퓨터 등과 같이 파손되기 쉬운 자재도 운송해야 합니다. 또한, 각 자재에 따라 적절한 차량도 필요합니다. 그런데 요즘 디젤 연료가 너무 비싸서 가능한 한 최단 경로로 움직여야 합니다. 도로 네트워크가 매우 복잡하지는 않지만 최단 경로를 알아내는 것은 복잡하므로 교수진들은 최단 경로를 구하는 프로그램을 작성하기로 했습니다.

입력

입력은 여러 테스트 케이스가 주어집니다. 테스트 케이스의 시작에는 공백으로 구분된 N, M, S, C가 주어집니다. 여기서 N은 도로 네트워크의 거점의 수(1 ≤ N ≤ 10,000)이고, M은 거점을 연결하는 도로의 수(1 ≤ M ≤ 50,000)입니다. S는 자재가 인수되는 곳의 거점 번호이고, C는 자재가 인도되는 곳의 거점 번호입니다. 입력이 전부 0이면 테스트 케이스 입력이 종료되고 이 줄은 처리하지 않습니다. 각 테스트 케이스 다음 M개 줄에 각 도로의 정보가 주어집니다. 각 줄에 공백으로 구분된 A, B, V가 주어집니다. A는 시작 거점, B는 도착 거점(일방통행), V는 도로의 이동 거리입니다. S에서 C로 이동할 수 있음이 보장됩니다.  

출력

S에서 C로 이동하는 최소 이동 거리를 한 줄로 출력합니다.

preview

댓글을 작성하려면 로그인해야 합니다.