DaoVoice JS 代码接入示例

原题

题目

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第(i)层楼((1 le i le N))上有一个数字(K_i(0 le K_i le N))。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：(3, 3 ,1 ,2 ,5)代表了(K_i(K_1=3,K_2=3,…))，从(1)楼开始。在(1)楼，按“上”可以到(4)楼，按“下”是不起作用的，因为没有(-2)楼。那么，从(A)楼到(B)楼至少要按几次按钮呢？

输入格式

共二行。

第一行为(3)个用空格隔开的正整数，表示(N,A,B(1≤N≤200, 1≤A,B≤N))。

第二行为(N)个用空格隔开的非负整数，表示(K_i)。

输出格式

一行，即最少按键次数,若无法到达，则输出(-1)。

输入样例

5 1 5
3 3 1 2 5

输出格式

3

思路

我们可以建个图，将(i)到(k_i)的距离存放到(f)数组里。
然后用(Floyd)算法找最小值。
注意初值：(f_{i,j}=∞(i≠j))

代码

var
  f:array[0..401,0..401] of int64;//定义f数组
  n,a,b,i,j,k,x:longint;//定义别的变量
begin
  readln(n,a,b);//读入n，a，b
  for i:=1 to n do for j:=1 to n do f[i,j]:=maxlongint;for i:=1 to n do f[i,i]:=0;//定初值
  for i:=1 to n do
    begin
      read(x);//读入x，也就是题目中的K_i
      if i+x<=n then f[i,i+x]:=1;if i-x>=1 then f[i,i-x]:=1;//如果不越界，则标记为1
    end;
  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if f[i,k]+f[k,j]<f[i,j] then
          f[i,j]:=f[i,k]+f[k,j];//Floyd不解释
  if f[a,b]=maxlongint then writeln(-1)//如果还是maxlongint，则不能到达，输出-1
    else writeln(f[a,b]);//否则输出a到b的最小值
end.