백준 20668 (C++) 카트라이더

최초 업로드: 2025-10-19 08:14:58

최근 수정 시간: 2025-10-19 08:14:58

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] 카트라이더

[문제 링크](https://www.acmicpc.net/problem/20668)

## 문제 설명

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

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

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

<그림 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자리까지 반올림하여 출력해야 한다.

## 풀이
위치와 속도 두 가지를 저장하는 배열로 최단 경로를 찾으면 되는 문제입니다. 소수를 여러 번 더하게 되면 오차가 생겨 모든 속도의 공배수를 곱해주어 계산 과정에서는 정수만 다루었습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX = 10'001;
const ll w = 11*10*9*8*7*6*5*4*3*2;

struct element {
    ll e, l, k;
};

vector<vector<element>> conn(MAX);
ll minDist[MAX][11];
bool inQueue[MAX][11];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    while(m--) {
        int s, e, l, k; cin >> s >> e >> l >> k;
        conn[s].push_back({e, l*w, k});
        conn[e].push_back({s, l*w, k});
    }

fill(&minDist[0][0], &minDist[MAX-1][11], LONG_LONG_MAX);
 queue<pair<int, int>> q; q.push({1, 1});
 minDist[1][1]=0;
 while(!q.empty()) {
 auto [cur, speed] = q.front(); q.pop();
 inQueue[cur][speed]=false;
 for(auto& [next, l, k]:conn[cur]) {
 for(int dx=-1;dx<=1;dx++) {
 int nextSpeed = speed+dx;
 if(nextSpeed<1 || nextSpeed>k) continue;

ll nextDist = minDist[cur][speed] + l/nextSpeed;
 if(minDist[next][nextSpeed]>nextDist) {
 minDist[next][nextSpeed] = nextDist;
 if(!inQueue[next][nextSpeed]) q.push({next, nextSpeed});
 inQueue[next][nextSpeed]=true;
 }
 }
 }
 }
 cout << setprecision(9) << fixed << *min_element(&minDist[n][0], &minDist[n][11])/(long double)w;
}
```