Trip Compulsion
면접 대비시간 제한24초메모리 제한1024 MB
가중치가 있는 무방향 그래프에서 start에서 end까지 가는 경로 중, 가장 긴 도로와 가장 짧은 도로의 길이 차이가 최소인 값을 구합니다.
문제
아주 괴짜인 한 사람이 넓은 동네를 번호가 붙은 교차로와 그 교차로들을 잇는 양방향 도로의 집합으로 모델링했다. 조금 섬뜩하게도 각 도로의 길이는 나노미터 단위로 재 두었다.
교차로에서 다른 교차로로 여행할 때마다 그 여행에 포함된 도로 중 가장 긴 도로와 가장 짧은 도로의 길이를 적어 두고, 두 값의 차이를 계산한다. 여행을 떠나기 전, 출발지와 도착지가 같은 모든 여행 가운데 가능한 차이의 최솟값을 알고 싶은 강한 충동이 들었다. 종이에 계산하려면 시간이 오래 걸리고, 여행도 조금 급하다(5시간 안에 출발해야 한다). 그래서 프로그램을 작성하기로 했다.
입력
첫 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 교차로의 수 N과 도로의 수 R이 공백으로 구분되어 주어진다. 각 테스트 케이스의 둘째 줄에는 여행의 출발 교차로 start와 도착 교차로 end가 공백으로 구분되어 주어진다. 이어지는 R개의 줄에는 도로의 시작 교차로 from, 도착 교차로 to, 길이 length가 공백으로 구분되어 주어진다. 도로는 양방향이다.
출력
각 테스트 케이스마다 가능한 차이의 최솟값을 나타내는 정수 하나를 한 줄에 출력한다. start에서 end로 가는 여행이 불가능하면 "NO PATH"를 한 줄에 출력한다(따옴표는 설명을 위한 것이다).
제한
- 2,000,000,000
- start와 end는 서로 다르다.