3 100 10000 100 101 102
35
1 34
0
3
3
3
...
3
99
100

i guess the answer is 201(1-35-34)
can DP give this answer? i think only ShortestPath can give this answer.

It's wrong answer. Right answer is 101.

I agree with you.

for example

1 2 100 100 100 1
4
2 3
2
3
99

when I used this input,my AC programm gave the answer 100 while the correct answer was 2

Distances are different(!) integer numbers given in ascending order.
So this test isn't correct.

Edited by author 10.05.2012 20:35

hey @bill125
if L2 < X ≤ L3  then cost is C3. // from table in problem statement
if  2 < X ≤ 100 then cost is 1 .
As X is 1 you can't use C3=1.