FilesExpand file tree

 main

/

Solution.cs

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

38 lines (36 loc) · 1.05 KB

 main

/

Solution.cs

Top

File metadata and controls

• Code
• Blame

38 lines (36 loc) · 1.05 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

31

32

33

34

35

36

37

38

public class Solution

{

public int ShortestPathLength(int[][] graph)

{

int n = graph.Length;

int fullBitMask = (1 << n) - 1;

Queue<(int, int)> queue = [];

bool[,] visited = new bool[n, fullBitMask + 1];

for (int i = 0; i < n; i++)

{

queue.Enqueue((i, (1 << i)));

visited[i, (1 << i)] = true;

}

int len = 0;

while (queue.Count > 0)

{

for (int i = queue.Count; i > 0; i--)

{

var (curr, bitMask) = queue.Dequeue();

if (bitMask == fullBitMask)

{

return len;

}

foreach (int next in graph[curr])

{

int newBitMask = bitMask | (1 << next);

if (visited[next, newBitMask]) continue;

visited[next, newBitMask] = true;

queue.Enqueue((next, bitMask | (1 << next)));

}

}

len++;

}

return len;

}

}