P1135奇怪的电梯

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,a,b;

long long dis[210][210];

int main(){

    //freopen("in","r",stdin);

    cin >> n >> a >> b;

    if(a == b){

        cout << 0 << endl;

        return 0;

    }

    for(int i = 0; i <= n; i++)

        for(int j = 0; j <= n; j++)

            dis[i][j] = 1e17;

        for(int i = 1; i <= n; i++){

            int x;

            cin >> x;

            if(i > x)

                dis[i][i - x] = 1;

            if( i + x <= n)

                dis[i][i + x] = 1;

        }

        for(int k = 1; k <= n; k++)

            for(int i = 1; i <= n; i++)

                for(int j = 1; j <= n; j++)

                    if(dis[i][j] > dis[i][k] + dis[k][j])

                        dis[i][j] = dis[i][k] + dis[k][j];

        if(dis[a][b] == 1e17)

            cout << "-1";

        else cout << dis[a][b];

    return 0;

}

for(int i = 0; i < G.vexnum; i++)

    for(int j = 0; j < G.vexnum; j++){

        D[i][j] = G.arcs[i][j];

        //如果i j之间又弧;将j的前驱置为i;

        if(D[i][j] < MaxInt && i != j)

            Path[i][j] = i;

        //否则-1；

        else Path[i][j] = -1;

    }

for(int k = 0; k < G.vexnum; k++)

    for(int i = 0; i < G.vexnum; i++)

        for(int j = 0; j < G.vexnum; j++)

            //从i经k到j的一条路径更短

            if(D[i][k] + D[k][j] < D[i][j]){

                D[i][j] = D[i][k] + D[k][j];

                //将j前驱改为k

                Path[i][j] = Path[k][j];

            }

巴特西

P1135奇怪的电梯

最新文章

热门文章