364. [HDU 1548] 奇怪的电梯

★ 输入文件：lift.in 输出文件：lift.out 简单对比
时间限制：1 s 内存限制：128 MB

【问题描述】

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

【输入格式】

输入文件共有二行，第一行为三个用空格隔开的正整数，表示 N,A,B(1≤N≤200, 1≤A,B≤N) ，第二行为 N 个用空格隔开的正整数，表示 Ki 。

【输出格式】

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

【样例输入】

5 1 5

3 3 1 2 5

【样例输出】

3

QAQ感觉自己简直是太无聊了  居然用最短路去做广搜的题QAQ
其实最短路的时间效率还是很棒的鸭（我还是用的迪杰斯特拉）
m*logm
这里的m最多也就400 这速度很棒诶~
这里的思路就是以A为起点   把每一层向上k层和向下k层的楼层的当前层连接起来
 然后还要判断一下有木有掉到地下去，或者直接飞上天了 Σ(⊙▽⊙"
其实也是很简单的啦 秒过
下面来贴一下我的不正常代码吧（就当是练一练模板啦）

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<vector>

#include<cmath>

#include<queue>

#define pa pair<int,int>

#define maxn 205

#define INF 0x3f3f3f3f

using namespace std;

int N,A,B;

vector<int> v[maxn];

int dis[maxn],vis[maxn];

priority_queue<pa,vector<pa>,greater<pa> > q;

void Dijkstra()

{

    for(int i=;i<=maxn;i++)

        dis[i]=INF;

    dis[A]=;

    q.push(make_pair(,A));

    while(!q.empty())

    {

        int x=q.top().second;

        q.pop();

        if(vis[x])

            continue;

        vis[x]=;

        for(int i=;i<v[x].size();i++)

        {

            int y=v[x][i];

            if(dis[y]>dis[x]+)

            {

                dis[y]=dis[x]+;

                q.push(make_pair(dis[y],y));

            }

        }

    }

}

int main()

{

    freopen("lift.in","r",stdin);

    freopen("lift.out","w",stdout);

    scanf("%d%d%d",&N,&A,&B);

    for(int i=;i<=N;i++)

    {

        int k;

        scanf("%d",&k);

        if(i+k<=N)

            v[i].push_back(i+k);

        if(i-k>)

            v[i].push_back(i-k);

    }

    Dijkstra();

    if(dis[B]==INF)

        printf("-1");

    else

        printf("%d",dis[B]);

    return ;

}

♪(^∇^*)加油哦~~~

巴特西

cogs 364. [HDU 1548] 奇怪的电梯 Dijkstra