jhwest2   2년 전

원본 문제의 풀이에 오류가 있고, github에 올라온 공식 정해 코드가 틀린 답을 내놓도록 하는 입력이 있습니다. 지문을 다음과 같이 수정해서 의도된 풀이가 통과하도록 하는 것이 좋아 보입니다.

수정 전 지문

As a mayor, you are allowed to change the altitude of at most one intersection to any non-negative real number. Using this opportunity, you want to minimize the total energy required to cycle from your house to the city hall.

수정 후 지문

As a mayor, you are allowed to change the altitude of at most one intersection to any non-negative real number. Using this opportunity, you want to minimize the total energy required to cycle from your house to the city hall. Note that you are allowed to change altitude during your journey to the city hall. This means you may first move around as much as you want, then change the altitude of a intersection, then sail your way through to the city hall.

문제가 생기는 것은 다음과 같은 입력이 주어지는 경우입니다. 

Input

5 4 1 5
0 50 100 200 300
1 2
2 3
2 4
4 5

Answer

30000

Output

20000.0
img.png

2번 정점을 고정한 뒤 최단 거리를 계산하는 경우, 의도된 풀이에서는 1번 정점 -> 2번 정점 -> 3번 정점 의 경로와 4번 정점 -> 5번 정점의 경로를 결합하여, 1 -> 2 (높이 50) -> 3 -> 2 (높이 150) -> 4 -> 5 로 이동하는 코스트 20000의 경로를 최적해로 계산하게 됩니다. 그러나 현재 지문대로라면, 먼저 높이를 변화시킨 뒤에 최단 경로를 계산해야 하므로, 위와 같은 경로는 valid한 경로가 아닙니다. 이를 고려한다면, 1 -> 2 (높이 100) -> 4 -> 5 로 이동할 때의 코스트인 30000이 정답이 되어야 합니다. 

즉, 한 정점 v를 고정하고, 시작점과 끝점 S와 T에서 v와 인접한 정점들로 가는 최단 경로들을 살펴볼 때, 그 경로가 정점 v를 지나는 경우를 고려하지 않는다는 사실이 의도된 풀이의 오류입니다. 이동 도중에 정점의 높이를 변화시킬 수 있도록 문제 조건을 수정하면 의도된 풀이가 맞게 되므로, 그렇게 수정할 것을 제안합니다. 

댓글을 작성하려면 로그인해야 합니다.