pstopia Notes for Problem Solving Contest

[D] Take-off Ramps

Codeforces Round #101 (Div. 2)

Problem

ramp 라는 것을 다시 써보자면 x-p 에서 x+d 까지 시간 t+p 만에 이동할 수 있는 수단이다. x-p 에서 x+d 로 향하는 가중치 t+p 인 간선을 이어주고 인접한 x좌표들에 양방향 간선을 이어준다. 그 뒤에 0에서 L까지 가는 최단거리를 구해주면 된다. rmq를 이용한 dp로도 해결할 수 있다.