스키 슬로프
시간 제한2초메모리 제한512 MB
길이와 최대 권장 속도가 주어진 활강로 방향 그래프에서 1번 지점에서 N번 지점까지 내려가며 총 노력 나누기 총 거리를 최소로 하는 경로를 찾는다.
문제
한 스키어가 산 정상에서 산기슭까지 스키를 타고 내려가려고 한다. 경로는 여러 가지가 있을 수 있으며, 경로마다 서로 다른 슬로프를 이용하고 몇몇 평지도 지난다. 슬로프를 내려갈 때 드는 노력은 슬로프의 길이와 스키 속도에 따라 달라진다. 슬로프마다 권장 최고 속도가 정해져 있다. 스키어는 단위 거리당 평균 노력(즉, 총 노력 나누기 총 이동 거리)을 최소로 하는 경로를 이용하려고 한다.
산의 슬로프 지도가 주어진다. 즉, 평지들과 이 평지들을 잇는 슬로프들이 주어진다. 슬로프에서는 아래쪽으로만 내려갈 수 있다. 슬로프마다 길이와 권장 최고 속도도 주어진다. 특정 슬로프를 내려갈 때 드는 노력은 다음 식으로 구한다.
e = d × (70 − s) (s ≤ 60), e = d × (s − 50) (s > 60)
여기서 e는 필요한 노력, d는 이동 거리, s는 이동 속도이다.
모든 슬로프에서 권장 최고 속도를 지키면서 산기슭에 도달하기 위해 스키어가 지불해야 하는 단위 거리당 평균 노력의 최솟값을 구해야 한다.
입력
입력에는 여러 테스트 케이스가 있을 수 있다. 입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 평지의 수 N (N ≤ 100)과 이들을 잇는 슬로프의 수 R (R ≤ 10000)이 주어진다. 평지는 1번부터 N번까지 번호가 매겨져 있다. 산의 정상과 기슭에 있는 평지는 각각 1번과 N번이다. 다음 R개 줄에는 슬로프의 위쪽 평지 번호, 아래쪽 평지 번호, 권장 최고 속도, 슬로프의 길이가 순서대로 주어진다.
출력
각 테스트 케이스마다 산 정상에서 기슭까지 내려가기 위해 필요한 단위 거리당 평균 노력의 최솟값을 소수점 둘째 자리까지 출력한다. 각 테스트 케이스의 출력은 서로 다른 줄에 있어야 한다.