Problem
题目大意:求顶点覆盖的最短路径。
https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/
An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1
) is given as graph
.
graph.length = N
, and j != i
is in the list graph[i]
exactly once, if and only if nodes i
and j
are connected.
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: [[1,2,3],[0],[0],[0]] Output: 4 Explanation: One possible path is [1,0,2,0,3]
Example 2:
Input: [[1],[0,2,4],[1,3,4],[2],[1,2]] Output: 4 Explanation: One possible path is [0,1,4,2,3]
Solution: BFS
Time complexity: O(n*2^n)
Space complexity: O(n*2^n)
C++
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 28 29 30 |
// Author: Huahua // Running time: 34 ms class Solution { public: int shortestPathLength(vector<vector<int>>& graph) { const int kAns = (1 << (graph.size())) - 1; queue<pair<int, int>> q; unordered_set<int> visited; // (cur_node << 16) | state for (int i = 0; i < graph.size(); ++i) q.push({i, 1 << i}); int steps = 0; while (!q.empty()) { int s = q.size(); while (s--) { auto p = q.front(); q.pop(); int n = p.first; int state = p.second; if (state == kAns) return steps; int key = (n << 16) | state; if (visited.count(key)) continue; visited.insert(key); for (int next : graph[n]) q.push({next, state | (1 << next)}); } ++steps; } return -1; } }; |
C++ / vector
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 28 29 30 |
// Author: Huahua // Running time: 10 ms class Solution { public: int shortestPathLength(vector<vector<int>>& graph) { const int n = graph.size(); const int kAns = (1 << n) - 1; queue<pair<int, int>> q; vector<vector<int>> visited(n, vector<int>(1 << n)); for (int i = 0; i < n; ++i) q.push({i, 1 << i}); int steps = 0; while (!q.empty()) { int s = q.size(); while (s--) { auto p = q.front(); q.pop(); int node = p.first; int state = p.second; if (state == kAns) return steps; if (visited[node][state]) continue; visited[node][state] = 1; for (int next : graph[node]) q.push({next, state | (1 << next)}); } ++steps; } return -1; } }; |
Related Problems
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment