Leetcode 847. Shortest Path Visiting All Nodes

[Woodyiiiiiii]

847. Shortest Path Visiting All Nodes

847. Shortest Path Visiting All Nodes

BFS + bitmask

这道题让我想起倒水问题：三个瓶子，容量分别是8、5、3升，初始第一瓶子里有8升水，如何才能构造出4升水？

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int all = (1 << n) - 1;
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            q.add(new int[]{1 << i, i, 0});
        }
        Map<Integer, Set<Integer>> visited = new HashMap<>();

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int state = cur[0], node = cur[1];
            for (int next : graph[node]) {
                int nextState = state | (1 << next);
                if (nextState == all) {
                    return cur[2] + 1;
                }
                if (visited.containsKey(nextState) && visited.get(nextState).contains(next)) {
                    continue;
                }
                q.add(new int[]{nextState, next, cur[2] + 1});
                visited.computeIfAbsent(nextState, k -> new HashSet<>()).add(next);
            }
        }

        return 0;
    }
}