Galactic Expedition

시간 제한8초메모리 제한1024 MB

요약
연결된 워프 포인트들로 이루어진 육각형 지도에서 연료가 제한된 우주선으로 탐사하며 이동한 총 거리를 보고한다.
난이도

보통10점 중 7점

유형
그래프, DFS, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

The inhabitants of Flatland have finally managed to invent spacecraft, and send a hexagon to embark on a brave journey to explore their two-dimensional outer space. Their goal is to reach an ancient relic that might teach them about the absurd idea of a "third dimension". You are head of operations at the home base, coordinating the movements of the spaceship.

The spaceship has enough fuel to travel a certain distance in space, but it can be refuelled at the home base if necessary. Chances are high that the spaceship does not have enough fuel to travel to the relic directly, but you quickly discover that outer space is scattered with wormholes that allow the spaceship to teleport from one location to another. Your team manages to draw out a map with all the warp-points they can observe, but it is impossible to figure out which pairs of warp-points are connected to each other, except by flying through them. Time to start exploring!

예제2

  1. 예제 1

    입력
    6 30
0 0
0 5
100 0
105 0
0 200
0 205

3

5
    예상 출력
    






2

4

6

  2. 예제 2

    입력
    6 20
0 0
0 5
95 100
-5 0
-100 0
100 100

5

4

1

3
    예상 출력
    






4

5

1

2

6