1548.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<stdio.h>
const int maxint=0x7fffffff;
int  length[210][210];
int  dist[210];
bool s[210];
int  n, a, b, x;
int main()
{
    int i, j, k, u;
    while(scanf("%d", &n) && n){
        scanf("%d %d", &a, &b);
        for(i = 1; i <= n; i++)
        {
            for(j = 1;j <= n; j++)
            {
                length[i][j] = 0;
            }
        }
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &x);
            if(i + x <= n && i + x > 0)
            {
                length[i][i + x] = 1;
            }
            if(i - x <= n && i - x > 0)
            {
                length[i][i - x] = 1;
            }
        }
        for(i = 1; i <= n; i++)
        {
            for(j = 1;j <= n; j++)
            {
                if(length[i][j] == 0)
                {
                    length[i][j] = maxint;
                }
            }
        }
        for(i = 1; i <= n; i++)
        {
            dist[i] = length[a][i];
            s[i]    =        false;
        }
        dist[a] =    0;
        s[a]    = true;
        for(i = 1; i < n; i++)
        {
            int min = maxint;
            for(j = 1; j <= n; j++)
            {
                if(s[j] == false && dist[j] < min)
                {
                    min  = dist[j];
                    u    =       j;
                }
            }
            if(min == maxint)
            {
                break;
            }
            s[u] = true;
            for(j = 1; j <= n; j++)
            {
                if(s[j] == false && length[u][j] < maxint && min + length[u][j] < dist[j])
                {
                    dist[j] = min + length[u][j];
                }
            }
        }
        if(dist[b] != maxint)
            printf("%d\n", dist[b]);
        else
            printf("-1\n");
    }
    return 0;
}