Optimization for Floyd Warshall Algorithm

help
, ,
1

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
2

anyone…?

3

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

1 Like
4

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

1 Like
5

thanks