洛谷 P1135 奇怪的电梯

2019-11-08 01:03:17

字体：大中小

来源：转载

供稿：网友

题目

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

题解

有很多方法，dfs，bfs，Floyd，等等都可以我写的是Floyd 读入每楼层可上下的层数时，就把每楼层到它可以到的楼层的路径权值赋为1，然后Floyd 时间复杂度 O(n*n*n)

代码

var a:array[-200..400]of longint; f:array[-200..400,-200..400]of longint; i,j,k,n,x,y,b:longint;begin readln(n,x,y); if x=y then begin writeln('0');halt;end; fillchar(f,sizeof(f),$7); b:=f[1,1]; for i:=1 to n do begin read(a[i]); if i+a[i]<=n then f[i,i+a[i]]:=1; if i-a[i]>=1 then f[i,i-a[i]]:=1; end; for i:=1 to n do f[i,i]:=0; 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]; if f[x,y]<>b then writeln(f[x,y]) else writeln('-1');end.

上一篇：【算法】程序猿不写代码是不对的20

下一篇：electron的入门学习