hdu 1548 A strange lift

男娘i 2021-12-22 11:39 93阅读 0赞

**SPFA**

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int maxn = 222;
    int k[maxn], ji[maxn];
    vector<int> abc[maxn];
    struct aaa{
        int node, tot;}dt[maxn*maxn];
    bool cmp(const aaa&a, const aaa&b){
        return a.tot < b.tot;}
    int main()
    {
        int N, A, B, i, j;
        while (~scanf("%d", &N))
        {
            if (N == 0) break;
            scanf("%d%d", &A, &B);
            for (i = 0; i < maxn; i++) ji[i] = 999999999, abc[i].clear();
            for (i = 1; i <= N; i++) scanf("%d", &k[i]);
            for (i = 1; i <= N; i++)
            {
                if (i + k[i] <= N) abc[i].push_back(i + k[i]);
                if (i - k[i] >= 1)abc[i].push_back(i - k[i]);
            }
            ji[A] = 0;dt[0].node = A;dt[0].tot = 0;int b = 0;
            for (i = 0; i <= b; i++)
            {
             for (j = 0; j < abc[dt[i].node].size(); j++)
                {
    
                    if (dt[i].tot + 1 < ji[abc[dt[i].node][j]])
                    {
                        b++;
                        dt[b].node = abc[dt[i].node][j];
                        dt[b].tot = dt[i].tot + 1;
                        ji[abc[dt[i].node][j]] = dt[i].tot + 1;
                    }
                }
            }
            if (ji[B] != 999999999)printf("%d\n", ji[B]);
            else printf("-1\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/zufezzt/p/4463828.html