LEET-T0847: Shortest Path Visiting All Nodes

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

typedef tuple<int, int, int> tiii;

const int N = 12 + 5;
const int M = (1 << 12) + 5;

vector<vector<int>> adj;
bool visited[N][M];

int shortestPathLength(vector<vector<int>> &adj){
    int nVertex = adj.size();
    queue<tiii> que;
    for(int i = 0; i < nVertex; ++i){
        visited[i][1 << i] = true;
        que.emplace(0, i, 1 << i);
    }
    while(!que.empty()){
        int d = get<0>(que.front());
        int u = get<1>(que.front());
        int us = get<2>(que.front());
        que.pop();
        if(us == (1 << nVertex) - 1){
            return d;
        }
        for(int v : adj[u]){
            int vs = us | (1 << v);
            if(!visited[v][vs]){
                visited[v][vs] = true;
                que.emplace(d + 1, v, vs);
            }
        }
    }
    return 0;
}

int main(){

    int nVertex, nEdge;
    scanf("%d%d", &nVertex, &nEdge);
    adj.assign(nVertex, vector<int>());
    for(int i = 1; i <= nEdge; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cout << shortestPathLength(adj);

    return 0;
}