Last active
June 10, 2022 01:44
-
-
Save satyajeetkrjha/a5061b8ebcda85d34b7a04cb7d2646da to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int shortestPathLength(vector<vector<int>>& graph) { | |
| int n = graph.size(); | |
| if( n == 1) | |
| return 0; | |
| queue <pair <int ,int> > q ; // node and bit state | |
| int finalstate = (1 << n )-1; | |
| vector <vector <int> > visited(n,vector <int>(finalstate+1,0)); | |
| for(int i =0 ;i<n;i++){ | |
| q.push({i,1 <<i}); | |
| } | |
| int ans =0; | |
| while(!q.empty()){ | |
| int sz = q.size(); | |
| ans ++; | |
| for(int i =0 ;i<sz;i++){ | |
| auto cur = q.front(); | |
| q.pop(); | |
| int node = cur.first ; | |
| int curnodestae = cur.second ; | |
| for(auto neighbor :graph[node]){ | |
| // instead of i'th say neighbor'th bit marked 1 | |
| int neighborstate = curnodestae | (1 << neighbor); | |
| if(visited[neighbor][neighborstate]){ | |
| continue ; | |
| } | |
| if(neighborstate == finalstate){ | |
| return ans ; | |
| } | |
| visited[neighbor][neighborstate] = 1; | |
| q.push({neighbor,neighborstate}); | |
| } | |
| } | |
| } | |
| return -1; | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment