mickypinata

LEET-T0847: Shortest Path Visiting All Nodes

Nov 30th, 2021
588
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef tuple<int, int, int> tiii;
  5.  
  6. const int N = 12 + 5;
  7. const int M = (1 << 12) + 5;
  8.  
  9. vector<vector<int>> adj;
  10. bool visited[N][M];
  11.  
  12. int shortestPathLength(vector<vector<int>> &adj){
  13.     int nVertex = adj.size();
  14.     queue<tiii> que;
  15.     for(int i = 0; i < nVertex; ++i){
  16.         visited[i][1 << i] = true;
  17.         que.emplace(0, i, 1 << i);
  18.     }
  19.     while(!que.empty()){
  20.         int d = get<0>(que.front());
  21.         int u = get<1>(que.front());
  22.         int us = get<2>(que.front());
  23.         que.pop();
  24.         if(us == (1 << nVertex) - 1){
  25.             return d;
  26.         }
  27.         for(int v : adj[u]){
  28.             int vs = us | (1 << v);
  29.             if(!visited[v][vs]){
  30.                 visited[v][vs] = true;
  31.                 que.emplace(d + 1, v, vs);
  32.             }
  33.         }
  34.     }
  35.     return 0;
  36. }
  37.  
  38. int main(){
  39.  
  40.     int nVertex, nEdge;
  41.     scanf("%d%d", &nVertex, &nEdge);
  42.     adj.assign(nVertex, vector<int>());
  43.     for(int i = 1; i <= nEdge; ++i){
  44.         int u, v;
  45.         scanf("%d%d", &u, &v);
  46.         adj[u].push_back(v);
  47.         adj[v].push_back(u);
  48.     }
  49.     cout << shortestPathLength(adj);
  50.  
  51.     return 0;
  52. }
  53.  
RAW Paste Data