94 分 佛洛依德求调
查看原帖
94 分 佛洛依德求调
1103658
TWstak楼主2024/9/14 21:31
#include<bits/stdc++.h>

using namespace std;

void Floyd(int n,vector<vector<int>>& A) {
    for (int k = 1; k <= n; k++) { // 中间节点k
        for (int i = 1; i <= n; i++) { // 起点i
            for (int j = 1; j <= n; j++) { // 终点j
                // 如果通过k可以缩短从i到j的距离,则更新距离和路径
                if (A[i][j] > A[i][k] + A[k][j]) {
                    A[i][j] = A[i][k] + A[k][j];
                }
            }
        }
    }
}

int main(){
	int n,a,b;
	cin >> n>>a>>b;
	vector<vector<int>> A(n+1,vector<int>(n+1,10000));
	vector<vector<int>>& map=A;
	for(int i=1;i<=n;i++){
		int temp;
		cin >> temp;
		
		if(i+temp>0&&i+temp<=n) A[i][i+temp]=1;
		if(i-temp>0&&i-temp<=n) A[i][i-temp]=1;
	}
	Floyd(n,map);
	cout<< ((A[a][b]==10000?-1:A[a][b]));
}
2024/9/14 21:31
加载中...