[LeetCode] Shortest Path Visiting All Nodes

847. Shortest Path Visiting All Nodes

You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
int shortestPathLength(vector<vector<int>>& graph) {
int n = graph.size();
if(n == 1) return 0;
vector<unordered_set<int>> visit(n);
//count, group, node
queue<array<int,3>> q;
int target = (1<<n) - 1;
for(int i = 0; i < n; i++) {
q.push({1, 1<<i, i});
visit[i].insert(1<<i);
}

while(!q.empty()) {
auto [count, group, node] = q.front(); q.pop();
for(auto next : graph[node]) {
int nextGroup = group | (1<<next);
if(visit[next].count(nextGroup)) continue;
visit[next].insert(nextGroup);
q.push({count + 1, nextGroup, next});
if(nextGroup == target) return count;
}
}
return -1;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/22/PS/LeetCode/shortest-path-visiting-all-nodes/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.