Алгоритм Флойда (теория графов)

int** floid(int** W,int n){
    vector<int**>D(n);
    int** A=new int*[n];
    for(int i=0;i<n;i++){
        A[i]=new int[n];
        for(int j=0;j<n;j++)
            A[i][j]=1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)
                A[i][j]=0;
            else{
                if(W[i][j]==0)
                    A[i][j]=100;
                else
                    A[i][j]=W[i][j];
            }
        }
    }
    D.push_back(A);
    int k=1;
    while(k<n){
        int** B=new int*[n];
        for(int i=0;i<n;i++){
            B[i]=new int[n];
            for(int j=0;j<n;j++)
                B[i][j]=1;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i!=j)
                    B[i][j]=min(D.back()[i][j],(D.back()[i][k]+D.back()[k][j]));
            }
        }
        k++;
        D.push_back(B);
    }
    return D.back();
}