hdu-1548

搜索做着做着成最短路径了。。

dij

本层可以直接到达的层数距离为1 否则为无穷大

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<sstream>
#include<time.h>
#include<utility>
#include<malloc.h>
#include<stdexcept>

using namespace std;

int n,a,b,m;
int p[210][210];
int q[210];
int d[210];
int vis[210];
int k;

void dij(int s)
{
    for(int i=1;i<=n;i++)
    {
        d[i] = p[s][i];
        vis[i] = 0;
    }

    d[s] = 0;
    vis[s] = 1;

    for(int i=1;i<=n;i++)
    {
        int minn = 10000000;
        k=s;
        for(int j =1;j<=n;j++)
        {
            if (!vis[j] && d[j] < minn)
            {
                minn = d[j];
                k=j;
            }
        }
        if (minn == 10000000)
            return ;
        vis[k] = 1;

        for(int j=1;j<=n;j++)
        {
            if (!vis[j] && (minn+p[k][j]) < d[j])
                d[j] = minn + p[k][j];
        }
    }
}

int main ()
{
    while (scanf("%d %d %d",&n,&a,&b)!=EOF && n)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if (i!=j)
                    p[i][j] = p[j][i] = 10000000;
                else
                    p[i][j] = 0;
            }
        }

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&q[i]);
            if (i + q[i] <=n)
            {
                p[i][q[i]+i] = 1;
            }
            if (i-q[i] >=1)
            {
                p[i][i-q[i]] = 1;
            }
        }
        dij(a);

        int anss = d[b];
        if (anss<10000000)
            cout<<anss<<endl;
        else
            printf("-1\n");
    }
    return 0;
}