백준 카트라이더(20668)

카트라이더

1. 힌트

1) 그래프의 정점을 $($정점 번호$,$ 현재 속도$)$로 모델링할 수 있습니다.

2) 모든 간선의 가중치에 $10!$이나 $lcm([1,10])$을 곱한 뒤 최단 경로의 길이에서 이를 나눠주면 실수 연산을 피할 수 있습니다.

3) 최단 경로의 길이를 나눠줄 때 정수부와 실수부를 따로 계산하면 정밀도를 높일 수 있습니다.

2. 접근

실수 오차때문에 고생해 본 문제는 처음입니다. 실수 연산을 피하기 위해서 여러가지 테크닉을 사용합니다.

1) 그래프 모델링

한 정점에 인접한 정점을 보려면 정점의 번호만 필요한 것이 아니라 그 정점에 도착했을 때(속도를 변경하기 전에)의 속도가 필요합니다. 그래야 간선의 속도 제한에 걸리는지 안 걸리는지 확인하고 인접한 정점을 확인할 수 있기 때문이죠. 다행히도 속도 제한 $K$는 $1\le K\le10$를 만족하므로 $10$보다 더 큰 속도는 무시해도 됩니다. 그런 속도로는 어떤 간선도 탈 수 없기 때문입니다.
따라서 그래프의 정점을 $($정점 번호$,$ 현재 속도$)$로 모델링하면 정점의 개수 $V$는 최대 $10^5$가 됩니다. $ElgV$의 다익스트라로 전혀 무리가 없죠.

2) 소수점 9자리까지 반올림하여 출력해야 한다.

그런데 문제는 출력 형식입니다. 무려 소수점 $9$자리까지 반올림을 해야하는데 만약 다익스트라에서 dist배열을 double로 정의하고 사용했다면 소수점 $9$자리까지의 정확도는 보장할 수 없습니다.
$64$비트 실수 자료형 double의 정밀도는 $15$자리이기 때문입니다.

가장 긴 최단경로의 길이를 생각해보겠습니다. 최단 경로는 모든 정점을 최대 한 번만 지나고, 간선의 길이 $L$은 최대 $10^5$이므로 가장 긴 최단경로의 길이는 약 $10^{10}$정도 될 것입니다. $11$자리의 숫자죠. 정수부만 해도 $11$자리를 사용하는데 소수점 아래 $9$자리까지는 택도 없습니다. 물론 여기서 $64$비트보다 더 큰 자료형을 정의해서 더 정확한 실수 연산을 구현할 수 도있지만 시간 안에 돌아갈지가 의문입니다.

3) 실수 연산 피하기

실수 연산이 일어나는 곳은 간선의 길이 $L$을 현재 속도로 나누는 부분입니다. 나누어 떨어지지 않을 수 있기 때문에 실수 연산이 필요하죠.

그런데 여기서 플레이어의 속도가 $1$에서 $10$사이임에 유의하여서 모든 간선의 길이 $L$에 $10!$이나 $lcm([1,10])$을 곱해놓으면 언제나 나누어 떨어지게 할 수 있습니다. 이러면 실수 연산을 사용할 필요 없이 정수 나눗셈 연산으로도 충분하죠. 그러고 난 다음에 맨 마지막에 간선에 곱해줬던 수들로 다시 나눠주면 됩니다.
최단 경로의 길이는 간선의 가중치의 합이고 $10!$을 따로 떼어서 생각할 수 있기 때문입니다. $\displaystyle\sum w_i\times10!=10!\displaystyle\sum w_i$

4) 정수부 실수부 나누어 계산하기

이렇게 구한 값을 $10!$로 나누어서 아래와 같이 출력하도록 제출해봤는데 또 바로 틀렸습니다. 왜 그런 것일까요?

// WA
System.out.printf("%.9f\n", dijkstra() / 3628800.);

그 이유는 2)에서 설명한 이유와 같습니다. 이번엔 모든 간선에 $10!$을 곱해주었으므로 최단 경로의 최대 길이가 $10^{10} \times 10!$이 되었습니다 이는 $17$자리 숫자입니다. double로는 불가능합니다. 이 때, 정수부 연산을 따로 먼저 하고 정밀도 $15$자리를 온전히 실수부 연산에만 사용하면 정확하게 계산할 수 있습니다.

// 모든 간선에 10!이 곱해져있으므로 10!로 나누어준다
// 실수 오차를 막기 위해서 정수부 연산과 실수부 연산을 분리한다.
long x = dijkstra();
System.out.print(x / 3628800);
x %= 3628800;
double y = (double)x / 3628800;
System.out.println(String.format("%.9f", y).toString().substring(1));

3. 구현

public class Main {
	static int N;
	static ArrayList<ArrayList<Tuple>> adj;
	
	// 정점의 개수는 최대 N * 10이고 간선의 길이는 최대 10^5
	// 그런데 간선의 길이에 모두 10!을 곱했으므로 10^5 * 10!
	// 가장 긴 최단경로의 길이는 10^10 * 10! 이므로 이보다 큰 값 사용
	static final long INF = Long.MAX_VALUE;
	
	static long dijkstra() {
		PriorityQueue<Tuple> pq = new PriorityQueue<>();
		pq.offer(new Tuple(1, 1, 0L));
		// (정점 번호, 그곳에 도착한 속도) 그래프 모델링
		long[][] dist = new long[N + 1][11];
		for (int i = 0; i < N + 1; i++)
			Arrays.fill(dist[i], INF);
		dist[1][1] = 0;
		while (!pq.isEmpty()) {
			Tuple t = pq.poll();
			int here = t.num; int speed = t.speed;
			long cost = t.cost;
			if (dist[here][speed] < cost) continue;
			for (Tuple edge : adj.get(here)) {
				for (int d = -1; d <= 1; d++) {
					int thereSpeed = speed + d;
					// 속도가 1 미만이 되거나 속도 제한을 넘는 경우
					if (!(1 <= thereSpeed && thereSpeed <= edge.limit))
						continue;
					int there = edge.num;
					// 간선에 10!을 곱했으므로 무조건 나누어 떨어짐
					long thereCost = cost + edge.cost / thereSpeed;
					if (dist[there][thereSpeed] > thereCost) {
						dist[there][thereSpeed] = thereCost;
						pq.offer(new Tuple(there, thereSpeed, thereCost));
					}
				}
			}
		}
		// 어떤 속도로 도착하건 최단 시간을 구한다
		long min = INF;
		for (int i = 1; i <= 10; i++)
			min = Math.min(min, dist[N][i]);
		return min;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		adj = new ArrayList<>(N);
		for (int i = 0; i <= N; i++) adj.add(new ArrayList<>());
		int M = Integer.parseInt(st.nextToken());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int l = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			adj.get(a).add(new Tuple(b, 3628800L * l, k));
			adj.get(b).add(new Tuple(a, 3628800L * l, k));
		}
		// 모든 간선에 10!이 곱해져있으므로 10!로 나누어준다
		// 실수 오차를 막기 위해서 정수부 연산과 실수부 연산을 분리한다.
		long x = dijkstra();
		System.out.print(x / 3628800);
		x %= 3628800;
		double y = (double)x / 3628800;
		System.out.println(String.format("%.9f", y).toString().substring(1));
	}

}

// 간선 혹은 pq에 넣을 정점을 표현하는 Tuple
class Tuple implements Comparable<Tuple> {
	int num, speed, limit;
	long cost;
	
	// 간선으로 사용하는 경우
	Tuple(int n, long c, int l) {
		num = n; cost = c; limit = l;
	}
	
	// pq에 넣을 정점으로 사용하는 경우
	Tuple(int n, int s, long c) {
		num = n; speed = s; cost = c;
	}
	
	@Override
	public int compareTo(Tuple o) { return Long.compare(cost, o.cost); }

}

1) 테스트 케이스

3 3
1 2 3 3
1 3 6 3
2 3 7 3
->3.000000000

2 1
1 2 3 3
->1.500000000

4 5
1 2 1 3
1 3 4 3
2 3 3 4
2 4 9 5
3 4 8 4
->3.416666667