2023-09-17 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 17

Description

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.

 

Example 1:

Input: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

Example 2:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

 

Constraints:

  • n == graph.length
  • 1 <= n <= 12
  • 0 <= graph[i].length < n
  • graph[i] does not contain i.
  • If graph[a] contains b, then graph[b] contains a.
  • The input graph is always connected.

Solution

pair<int, int> getState(int state) {
  int visited = ((1 << 12) - 1) & state;
  state >>= 12;
  int current;
  for(int i = 0; i < 12; ++i) {
    if((1 << i) & state) current = i;
  }
  return {current, visited};
}
inline constexpr int genState(int current, int visited) {
  return (1 << (current + 12)) | visited;
}
class Solution {
public:
  int shortestPathLength(vector<vector<int>>& graph) {
    int len = graph.size();
    const int TARGET = (1 << len) - 1;
    queue<int> q;
    set<int> states;
    for(int i = 0; i < len; ++i) {
      int state = genState(i, (1 << i));
      q.push(state);
      states.insert(state);
    }
    int answer = 0;
    while(q.size()) {
      int sz = q.size();
      for(int _ = 0; _ < sz; ++_) {
        auto [current, visited] = getState(q.front());
        q.pop();
        if(visited == TARGET) return answer;
        for(auto nxt : graph[current]) {
          int state = genState(nxt, visited | (1 << nxt));
          if(states.count(state))continue;
          states.insert(state);
          q.push(state);
        }
      }
      answer += 1;
    }
    return -1;
  }
};

// Accepted
// 51/51 cases passed (99 ms)
// Your runtime beats 42.96 % of cpp submissions
// Your memory usage beats 51.19 % of cpp submissions (17.2 MB)
Algorithm