Advertisement
YEZAELP

LeetCode: Shortest Path Visiting All Nodes

Dec 1st, 2021 (edited)
283
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.    
  4.     using pi = pair <int, int>;
  5.     using pii = pair <int, pi>;
  6.    
  7.     int shortestPathLength(vector<vector<int>> &graph){
  8.         int n = graph.size();
  9.         vector <int> g[n];
  10.         for(int u=0;u<=n-1;u++){
  11.             for(auto v: graph[u]){
  12.                 g[u].push_back(v);
  13.             }
  14.         }
  15.        
  16.         int Bit = (1 << n) - 1;
  17.         vector < vector <int> > dis(n, vector <int> (Bit + 1, 1e9));
  18.         vector < vector <bool> > vs(n, vector <bool> (Bit + 1, false));
  19.         queue <pii> q;
  20.         for(int u=0;u<=n-1;u++){
  21.             dis[u][1 << u] = 0;
  22.             q.push({0, {u, 1 << u}});
  23.         }
  24.        
  25.         while(!q.empty()){
  26.             int d = q.front().first;
  27.             int u = q.front().second.first;
  28.             int bit = q.front().second.second;
  29.             q.pop();
  30.             if(vs[u][bit]) continue; vs[u][bit] = true;
  31.             if(bit == Bit) return d;
  32.             for(auto v: g[u]){
  33.                 int nxtbit = bit | (1 << v);
  34.                 if(!vs[v][nxtbit] and 1 + d < dis[v][nxtbit]){
  35.                     dis[v][nxtbit] = d + 1;
  36.                     q.push({d + 1, {v, nxtbit}});
  37.                 }
  38.             }
  39.         }
  40.        
  41.         return -1;
  42.     }
  43. };
Advertisement
RAW Paste Data Copied
Advertisement