시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 219 31 25 17.361%

문제

카트라이더는 플레이어가 주어진 맵에서 차를 타고 출발 지점에서 시작해 경로를 따라 목적지까지 최대한 빨리 도착하는 것이 목표인 게임이다.

이때 맵에는 다양한 지름길이 존재하여 목적지까지 갈 수 있는 방법은 다양하다.

카트라이더의 맵은 다음과 같은 무방향 가중 그래프로 나타낼 수 있다.

<그림 1> 예제 입력1 예시

카트라이더는 레이싱 게임이기 때문에 플레이어는 일정 속도로 이동한다.

플레이어는 1의 속도로 출발지에서 생성되고, 출발지를 포함한 모든 정점을 방문할 때마다 속도를 1 증가, 1 감소, 또는 그대로 유지할 수 있다. 시작 직후 출발지에서 속도를 올리는 것도 가능하다.

속도는 1 미만으로 내려갈 수 없다.

정점 사이의 간선은 길을 뜻하고, 간선은 길이와 속도 제한을 가진다.

간선을 통과할 때에는 길이를 속도로 나눈 만큼의 시간이 소모된다.

길의 코스가 어려운 구간에서는 속도가 빠르면 벽에 충돌할 수 있기 때문에 속도 제한을 넘긴 상태일 때에는 그 길을 사용할 수 없다.

카트라이더 맵이 주어졌을 때 출발 지점에서 목적지까지 이동할 때 걸리는 최단 시간을 구하여라.

입력

첫번째 줄에는 정점의 개수 N 과 간선의 개수 M 이 차례로 주어진다. (2 ≤ N ≤ 10,000, 1 ≤ M ≤ 100,000)

다음 개의 줄에는 각 간선의 정보인 4개의 정수가 주어진다.

간선이 연결하는 정점 A, 정점 B, 간선의 길이 L, 속도 제한 K 가 차례로 주어진다. (1 <= A, B <= N, 1 <= L <= 100,000, 1 <= K <= 10)

1번 정점은 출발지이고, 번 정점은 목적지이다.

입력으로 주어진 그래프는 출발지에서 목적지까지 이동할 수 있는 경로가 항상 존재한다.

출력

출발지에서 목적지까지 이동하는데 필요한 최소 시간을 출력해라.

출력 값은 정확히 소수점 9자리까지 반올림하여 출력해야 한다.

예제 입력 1

3 3
1 2 2 3
2 3 6 3
1 3 7 3

예제 출력 1

3.000000000

맨 처음 1번 노드에서 속도를 1 늘려 2의 속도로 1번 노드에서 2번 노드로 이동하고, 3의 속도로 2번 노드에서 3번 노드로 이동한다.

힌트

double, long double 등의 실수형을 사용하여 출력할 경우 유효 숫자 범위로 인해 틀릴 수 있다.

출처

University > 경인지역 6개대학 연합 프로그래밍 경시대회 > shake! 2020 D번