代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
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
.graph[a]
contains b
, then graph[b]
contains a
.class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
q = deque()
vis = set()
for i in range(n):
q.append((i, 1 << i))
vis.add((i, 1 << i))
ans = 0
while 1:
for _ in range(len(q)):
i, st = q.popleft()
if st == (1 << n) - 1:
return ans
for j in graph[i]:
nst = st | 1 << j
if (j, nst) not in vis:
vis.add((j, nst))
q.append((j, nst))
ans += 1
class Solution {
public int shortestPathLength(int[][] graph) {
int n = graph.length;
Deque<int[]> q = new ArrayDeque<>();
boolean[][] vis = new boolean[n][1 << n];
for (int i = 0; i < n; ++i) {
q.offer(new int[] {i, 1 << i});
vis[i][1 << i] = true;
}
for (int ans = 0;; ++ans) {
for (int k = q.size(); k > 0; --k) {
var p = q.poll();
int i = p[0], st = p[1];
if (st == (1 << n) - 1) {
return ans;
}
for (int j : graph[i]) {
int nst = st | 1 << j;
if (!vis[j][nst]) {
vis[j][nst] = true;
q.offer(new int[] {j, nst});
}
}
}
}
}
}
class Solution {
public:
int shortestPathLength(vector<vector<int>>& graph) {
int n = graph.size();
queue<pair<int, int>> q;
bool vis[n][1 << n];
memset(vis, false, sizeof(vis));
for (int i = 0; i < n; ++i) {
q.emplace(i, 1 << i);
vis[i][1 << i] = true;
}
for (int ans = 0;; ++ans) {
for (int k = q.size(); k; --k) {
auto [i, st] = q.front();
q.pop();
if (st == (1 << n) - 1) {
return ans;
}
for (int j : graph[i]) {
int nst = st | 1 << j;
if (!vis[j][nst]) {
vis[j][nst] = true;
q.emplace(j, nst);
}
}
}
}
}
};
func shortestPathLength(graph [][]int) int {
n := len(graph)
q := [][2]int{}
vis := make([][]bool, n)
for i := range vis {
vis[i] = make([]bool, 1<<n)
vis[i][1<<i] = true
q = append(q, [2]int{i, 1 << i})
}
for ans := 0; ; ans++ {
for k := len(q); k > 0; k-- {
p := q[0]
q = q[1:]
i, st := p[0], p[1]
if st == (1<<n)-1 {
return ans
}
for _, j := range graph[i] {
nst := st | 1<<j
if !vis[j][nst] {
vis[j][nst] = true
q = append(q, [2]int{j, nst})
}
}
}
}
}
function shortestPathLength(graph: number[][]): number {
const n = graph.length;
const q: number[][] = [];
const vis: boolean[][] = new Array(n).fill(false).map(() => new Array(1 << n).fill(false));
for (let i = 0; i < n; ++i) {
q.push([i, 1 << i]);
vis[i][1 << i] = true;
}
for (let ans = 0; ; ++ans) {
for (let k = q.length; k; --k) {
const [i, st] = q.shift()!;
if (st === (1 << n) - 1) {
return ans;
}
for (const j of graph[i]) {
const nst = st | (1 << j);
if (!vis[j][nst]) {
vis[j][nst] = true;
q.push([j, nst]);
}
}
}
}
}
use std::collections::VecDeque;
impl Solution {
#[allow(dead_code)]
pub fn shortest_path_length(graph: Vec<Vec<i32>>) -> i32 {
let n = graph.len();
let mut vis = vec![vec![false; 1 << n]; n];
let mut q = VecDeque::new();
// Initialize the queue
for i in 0..n {
q.push_back(((i, 1 << i), 0));
vis[i][1 << i] = true;
}
// Begin BFS
while !q.is_empty() {
let ((i, st), count) = q.pop_front().unwrap();
if st == (1 << n) - 1 {
return count;
}
// If the path has not been visited
for j in &graph[i] {
let nst = st | (1 << *j);
if !vis[*j as usize][nst] {
q.push_back(((*j as usize, nst), count + 1));
vis[*j as usize][nst] = true;
}
}
}
-1
}
}
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
def f(state):
return sum(((state >> i) & 1) == 0 for i in range(n))
q = []
dist = [[inf] * (1 << n) for _ in range(n)]
for i in range(n):
heappush(q, (f(1 << i), i, 1 << i))
dist[i][1 << i] = 0
while q:
_, u, state = heappop(q)
if state == (1 << n) - 1:
return dist[u][state]
for v in graph[u]:
nxt = state | (1 << v)
if dist[v][nxt] > dist[u][state] + 1:
dist[v][nxt] = dist[u][state] + 1
heappush(q, (dist[v][nxt] + f(nxt), v, nxt))
return 0
class Solution {
private int n;
public int shortestPathLength(int[][] graph) {
n = graph.length;
int[][] dist = new int[n][1 << n];
for (int i = 0; i < n; ++i) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
for (int i = 0; i < n; ++i) {
q.offer(new int[] {f(1 << i), i, 1 << i});
dist[i][1 << i] = 0;
}
while (!q.isEmpty()) {
int[] p = q.poll();
int u = p[1], state = p[2];
if (state == (1 << n) - 1) {
return dist[u][state];
}
for (int v : graph[u]) {
int nxt = state | (1 << v);
if (dist[v][nxt] > dist[u][state] + 1) {
dist[v][nxt] = dist[u][state] + 1;
q.offer(new int[] {dist[v][nxt] + f(nxt), v, nxt});
}
}
}
return 0;
}
private int f(int state) {
int ans = 0;
for (int i = 0; i < n; ++i) {
if (((state >> i) & 1) == 0) {
++ans;
}
}
return ans;
}
}
class Solution {
public:
int n;
int shortestPathLength(vector<vector<int>>& graph) {
n = graph.size();
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
vector<vector<int>> dist(n, vector<int>(1 << n, INT_MAX));
for (int i = 0; i < n; ++i) {
q.push({f(1 << i), i, 1 << i});
dist[i][1 << i] = 0;
}
while (!q.empty()) {
auto [_, u, state] = q.top();
q.pop();
if (state == (1 << n) - 1) return dist[u][state];
for (int v : graph[u]) {
int nxt = state | (1 << v);
if (dist[v][nxt] > dist[u][state] + 1) {
dist[v][nxt] = dist[u][state] + 1;
q.push({dist[v][nxt] + f(nxt), v, nxt});
}
}
}
return 0;
}
int f(int state) {
int ans = 0;
for (int i = 0; i < n; ++i)
if (((state >> i) & 1) == 0)
++ans;
return ans;
}
};
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。