시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 548 | 86 | 67 | 15.914% |
카트라이더는 플레이어가 주어진 맵에서 차를 타고 출발 지점에서 시작해 경로를 따라 목적지까지 최대한 빨리 도착하는 것이 목표인 게임이다.
이때 맵에는 다양한 지름길이 존재하여 목적지까지 갈 수 있는 방법은 다양하다.
카트라이더의 맵은 다음과 같은 무방향 가중 그래프로 나타낼 수 있다.
<그림 1> 예제 입력1 예시
카트라이더는 레이싱 게임이기 때문에 플레이어는 일정 속도로 이동한다.
플레이어는 1의 속도로 출발지에서 생성되고, 출발지를 포함한 모든 정점을 방문할 때마다 속도를 1 증가, 1 감소, 또는 그대로 유지할 수 있다. 시작 직후 출발지에서 속도를 올리는 것도 가능하다.
속도는 1 미만으로 내려갈 수 없다.
정점 사이의 간선은 길을 뜻하고, 간선은 길이와 속도 제한을 가진다.
간선을 통과할 때에는 길이를 속도로 나눈 만큼의 시간이 소모된다.
길의 코스가 어려운 구간에서는 속도가 빠르면 벽에 충돌할 수 있기 때문에 속도 제한을 넘긴 상태일 때에는 그 길을 사용할 수 없다.
카트라이더 맵이 주어졌을 때 출발 지점에서 목적지까지 이동할 때 걸리는 최단 시간을 구하여라.
첫번째 줄에는 정점의 개수 N 과 간선의 개수 M 이 차례로 주어진다. (2 ≤ N ≤ 10,000, 1 ≤ M ≤ 100,000)
다음 M 개의 줄에는 각 간선의 정보인 4개의 정수가 주어진다.
간선이 연결하는 정점 A, 정점 B, 간선의 길이 L, 속도 제한 K 가 차례로 주어진다. (1 <= A, B <= N, 1 <= L <= 100,000, 1 <= K <= 10)
1번 정점은 출발지이고, N 번 정점은 목적지이다.
입력으로 주어진 그래프는 출발지에서 목적지까지 이동할 수 있는 경로가 항상 존재한다.
출발지에서 목적지까지 이동하는데 필요한 최소 시간을 출력해라.
출력 값은 정확히 소수점 9자리까지 반올림하여 출력해야 한다.
3 3 1 2 2 3 2 3 6 3 1 3 7 3
3.000000000
맨 처음 1번 노드에서 속도를 1 늘려 2의 속도로 1번 노드에서 2번 노드로 이동하고, 3의 속도로 2번 노드에서 3번 노드로 이동한다.
double, long double 등의 실수형을 사용하여 출력할 경우 유효 숫자 범위로 인해 틀릴 수 있다.
University > 경인지역 6개대학 연합 > shake! 2020 D번