# Optimization for Floyd Warshall Algorithm

I am trying to solve Floyd Warshall | Practice | GeeksforGeeks but i am getting tle. The required time complexity is O(n^3) and i am pretty sure that my code’s time complexity is O(n^3) only.

Here’s the code

``````// { Driver Code Starts
//Initial template for C++

#include<bits/stdc++.h>
using namespace std;

// } Driver Code Ends
//User function template for C++

class Solution {
public:
void shortest_distance(vector<vector<int>>&matrix){
// Code here
int n = matrix.size();

for(int k=0; k<n; k++){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(matrix.at(i).at(k) != -1 && matrix.at(k).at(j) != -1){
if(matrix.at(i).at(j) == -1){
matrix.at(i).at(j) = matrix.at(i).at(k)+matrix.at(k).at(j);
}
else{
matrix.at(i).at(j) = min(matrix.at(i).at(j), matrix.at(i).at(k)+matrix.at(k).at(j));
}
}
}
}
}

}
};

// { Driver Code Starts.
int main(){
int tc;
cin >> tc;
while(tc--){
int n;
cin >> n;
vector<vector<int>>matrix(n, vector<int>(n, -1));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> matrix[i][j];
}
}
Solution obj;
obj.shortest_distance(matrix);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cout << matrix[i][j] << " ";
}
cout << "\n";
}
}
return 0;
}  // } Driver Code Ends
``````

anyone…?

You could try using e.g `matrix[i][j]` instead of `matrix.at(i).at(j)` throughout your solution.

1 Like

Yes it got accepted now. I had no idea `at()` is not efficient.

1 Like

thanks