HDOJ_1548 上楼梯 DJ

这个题，我使用最短路的方法解得，初始化每段路为1 ，这样只要找出荷最小的就最佳方法。初始化时，用上下来初始MAP

#include<stdio.h>
#define MAX (1<<20)
#define MAX_1 1001
int n,A,B,map[MAX_1][MAX_1],dis[MAX_1];
bool vista[MAX_1];
void dilskta(int k)
{
    int i,j,u,min;
    for(i=1;i<=n;++i)
    {
        vista[i]=false;
        dis[i]=map[i][k];
    }
    for(i=2;i<=n;++i)
    {
        min=MAX;
        for(j=1;j<=n;++j)
        {
            if(!vista[j]&&min>dis[j])
            {
                u=j;
                min=dis[j];
            }
        }
        vista[u]=true;
        for(j=1;j<=n;++j)
        {
            if(!vista[j]&&dis[j]>min+map[j][u])
            {
                dis[j]=min+map[j][u];
            }
        }
    }
}

int main()
{
    int i,j,A,B,move[MAX_1],down,up;
    while(scanf("%d",&n),n)
    {
        scanf("%d%d",&A,&B);
        for(i=1;i<=n;++i)
            scanf("%d",&move[i]);
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                map[i][j]=i==j?0:MAX;
        for(i=1;i<=n;++i)
        {
            up=i+move[i];
            down=i-move[i];
            if(up<=n)
                map[i][up]=1;
            if(down>=1)
                map[i][down]=1;
        }
        dilskta(B);
        if(dis[A]!=MAX)
         printf("%d\n",dis[A]);
        else
           printf("-1\n");
    }
    return 0;
}