BOJ 17526 Star Trek

문제 링크:

문제 내용

수직선 위에 $n$개의 점이 있습니다 ($3 \le n \le 100\;000$). 각각의 이웃한 점들 사이의 거리 $n-1$개가 주어집니다. (거리 $d$의 범위: $1 \le d \le 1000$)

1번 점에서 $n$번 점으로 이동하려고 하는데, 각 점에서 출발하는 교통 수단을 이용할 수 있습니다. 각 교통수단은 아무 때나 출발할 수 있지만, 각각 준비 시간과 이동 속도가 다릅니다. 이동 속도는 “거리 1을 이동하는 데 걸리는 시간"으로 주어집니다. 어떤 점에서 교통 수단을 갈아타는 데에는 주어진 준비 시간 이외의 추가 시간은 들지 않습니다. (준비 시간 $p$의 범위: $0 \le p \le 10^9$, 속도 값 $s$의 범위: $1 \le s \le 10^5$)

이때 1번 점에서 $n$번 점으로 이동하는 데 걸리는 최소 시간을 구하세요.

문제 풀이