[洛谷 1135,HDU 1548]奇怪的电梯

题目链接

https://www.luogu.org/problem/P1135

http://acm.hdu.edu.cn/showproblem.php?pid=1548

题解

当然可以用搜索的方法来解决这道题，但我们也可以从图论的角度来看待这个问题。

如果一个楼层能够直接坐电梯到达另一个楼层，就从该楼层向它通向的楼层连一条有向边。于是这道题就变成了求 \(A\) 到 \(B\) 的最短路。

注意到 \(N \leq 200\)，用 floyd 就可以解决问题。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int k[205],f[205][205];
int main()
{
 memset(f,INF,sizeof(f));
 int n,a,b;
 scanf("%d%d%d",&n,&a,&b);
 for(int i=1;i<=n;i++)
  f[i][i]=0;
 for(int i=1;i<=n;i++)
 {
  scanf("%d",&k[i]);
  if(k[i]+i<=b)f[i][k[i]+i]=1;
  if(i-k[i]>=1)f[i][i-k[i]]=1;
 }
 for(int k=1;k<=n;k++)
  for(int i=1;i<=n;i++)
   for(int j=1;j<=n;j++)
    f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
 if(f[a][b]==INF)printf("-1");
 else printf("%d",f[a][b]);
 return 0;
}