Swim In Rising Water
Swim In Rising Water Problem
You are given a square 2D matrix grid of distinct integers, where grid[i][j] represents the elevation at position (i, j).
Rain starts at time = 0, causing the water level to rise. At time t, the water level becomes t across the entire grid.
You can move horizontally or vertically between two adjacent squares if their elevations are less than or equal to the water level at time t.
Starting from the top-left square (0, 0), return the minimum time required to reach the bottom-right square (n – 1, n – 1).
Examples related to Swim In Rising Water Problem
Example 1:
Illustration:
Input: grid = [[0,1],[2,3]]
Output: 3
Explanation: For a path to exist to the bottom right square grid[1][1] the water elevation must be at least 3.
At time t = 3, the water level is 3.
Output: 3
Explanation: For a path to exist to the bottom right square grid[1][1] the water elevation must be at least 3.
At time t = 3, the water level is 3.
Example 2:
Input: times =grid = [
[0,1,2,10],
[9,14,4,13],
[12,3,8,15],
[11,5,7,6]]
]
Output: 8
Explanation: Water level must be at least 8 to reach the bottom right square.
Path is [0, 1, 2, 4, 8, 7, 6].
[0,1,2,10],
[9,14,4,13],
[12,3,8,15],
[11,5,7,6]]
]
Output: 8
Explanation: Water level must be at least 8 to reach the bottom right square.
Path is [0, 1, 2, 4, 8, 7, 6].
Constraints:
- grid.length == grid[i].length
- 1 <= grid.length <= 50
- 0 <= grid[i][j] < n^2
Hints to solve Swim In Rising Water Problem
Recommended Time & Space Complexity
Aim for a solution with a time complexity of O((n²) log n) and a space complexity of O(n²), where n is the number of rows or columns in the grid.
Hint 1:
Imagine the grid as a graph where each cell is a node. Movement to an adjacent cell is possible if the current time is at least equal to the adjacent cell’s elevation.
Swimming itself doesn’t take time, but you may need to wait at a cell for the water level to rise enough.
Notice that the goal is to find the optimal path from (0, 0) to (n-1, n-1).
Could a greedy approach help?
Hint 2:
The time taken to traverse a path depends on the highest elevation along the path.
To minimize this time, you need to find a path where the maximum elevation is as small as possible.
Can a shortest-path algorithm be adapted to solve this problem?
Hint 3:
Use Dijkstra’s Algorithm with a Min-Heap. Initialize a Min-Heap and a distance matrix filled with infinity.
Start from the source (0, 0), and for every path, track the maximum elevation encountered. Use this maximum elevation as the key for comparisons.
When you reach the destination (n-1, n-1), return the smallest maximum elevation recorded along the path.
Methods to Solve Swim In Rising Water Problem
There are mainly 5 approach to solve Swim In Rising Water problem:
- Brute Force Method
- Depth First Search Method
- Binary Search + DFS
- Dijkstra’s Algorithm
- Kruskal’s Algorithm
1. Brute Force Method
Explore all possible paths from the start to the end, tracking the maximum elevation along each path. Return the minimum of these maximums. This method is simple but inefficient for larger grids due to its exhaustive nature.
- Time complexity: O(4^{n^{2}})
- Space complexity: O(n^2)
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
int swimInWater(vector>& grid) {
int n = grid.size();
vector> visit(n, vector(n, false));
return dfs(grid, visit, 0, 0, 0);
}
private:
int dfs(vector>& grid, vector>& visit,
int r, int c, int t) {
int n = grid.size();
if (r < 0 || c < 0 || r >= n || c >= n || visit[r][c]) {
return 1000000;
}
if (r == n - 1 && c == n - 1) {
return max(t, grid[r][c]);
}
visit[r][c] = true;
t = max(t, grid[r][c]);
int res = min(min(dfs(grid, visit, r + 1, c, t),
dfs(grid, visit, r - 1, c, t)),
min(dfs(grid, visit, r, c + 1, t),
dfs(grid, visit, r, c - 1, t)));
visit[r][c] = false;
return res;
}
};
Java
public class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
boolean[][] visit = new boolean[n][n];
return dfs(grid, visit, 0, 0, 0);
}
private int dfs(int[][] grid, boolean[][] visit,
int r, int c, int t) {
int n = grid.length;
if (r < 0 || c < 0 || r >= n || c >= n || visit[r][c]) {
return 1000000;
}
if (r == n - 1 && c == n - 1) {
return Math.max(t, grid[r][c]);
}
visit[r][c] = true;
t = Math.max(t, grid[r][c]);
int res = Math.min(Math.min(dfs(grid, visit, r + 1, c, t),
dfs(grid, visit, r - 1, c, t)),
Math.min(dfs(grid, visit, r, c + 1, t),
dfs(grid, visit, r, c - 1, t)));
visit[r][c] = false;
return res;
}
}
Python
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
visit = [[False] * n for _ in range(n)]
def dfs(node, t):
r, c = node
if min(r, c) < 0 or max(r, c) >= n or visit[r][c]:
return 1000000
if r == (n - 1) and c == (n - 1):
return max(t, grid[r][c])
visit[r][c] = True
t = max(t, grid[r][c])
res = min(dfs((r + 1, c), t),
dfs((r - 1, c), t),
dfs((r, c + 1), t),
dfs((r, c - 1), t))
visit[r][c] = False
return res
return dfs((0, 0), 0)
JavaScript
class Solution {
/**
* @param {number[][]} grid
* @return {number}
*/
swimInWater(grid) {
const n = grid.length;
const visit = Array.from({ length: n }, () =>
Array(n).fill(false));
const dfs = (r, c, t) => {
if (r < 0 || c < 0 || r >= n ||
c >= n || visit[r][c]) {
return 1000000;
}
if (r === n - 1 && c === n - 1) {
return Math.max(t, grid[r][c]);
}
visit[r][c] = true;
t = Math.max(t, grid[r][c]);
const res = Math.min(
Math.min(dfs(r + 1, c, t),
dfs(r - 1, c, t)),
Math.min(dfs(r, c + 1, t),
dfs(r, c - 1, t))
);
visit[r][c] = false;
return res;
}
return dfs(0, 0, 0);
}
}
2. Depth First Search (DFS) Method
Use DFS to explore paths from the top-left to the bottom-right of the grid. Track the maximum elevation encountered along the way and backtrack when necessary to find the minimum maximum elevation path.
- Time complexity: O(n^4)
- Space complexity: O(n^2)
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
int swimInWater(vector>& grid) {
int n = grid.size();
vector> visit(n, vector(n, false));
int minH = grid[0][0], maxH = grid[0][0];
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
maxH = max(maxH, grid[row][col]);
minH = min(minH, grid[row][col]);
}
}
for (int t = minH; t < maxH; t++) {
if (dfs(grid, visit, 0, 0, t)) {
return t;
}
for (int r = 0; r < n; r++) {
fill(visit[r].begin(), visit[r].end(), false);
}
}
return maxH;
}
private:
bool dfs(vector>& grid, vector>& visit,
int r, int c, int t) {
if (r < 0 || c < 0 || r >= grid.size() ||
c >= grid.size() || visit[r][c] || grid[r][c] > t) {
return false;
}
if (r == grid.size() - 1 && c == grid.size() - 1) {
return true;
}
visit[r][c] = true;
return dfs(grid, visit, r + 1, c, t) ||
dfs(grid, visit, r - 1, c, t) ||
dfs(grid, visit, r, c + 1, t) ||
dfs(grid, visit, r, c - 1, t);
}
};
Java
public class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
boolean[][] visit = new boolean[n][n];
int minH = grid[0][0], maxH = grid[0][0];
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
maxH = Math.max(maxH, grid[row][col]);
minH = Math.min(minH, grid[row][col]);
}
}
for (int t = minH; t < maxH; t++) {
if (dfs(grid, visit, 0, 0, t)) {
return t;
}
for (int r = 0; r < n; r++) {
Arrays.fill(visit[r], false);
}
}
return maxH;
}
private boolean dfs(int[][] grid, boolean[][] visit, int r, int c, int t) {
if (r < 0 || c < 0 || r >= grid.length ||
c >= grid.length || visit[r][c] || grid[r][c] > t) {
return false;
}
if (r == grid.length - 1 && c == grid.length - 1) {
return true;
}
visit[r][c] = true;
return dfs(grid, visit, r + 1, c, t) ||
dfs(grid, visit, r - 1, c, t) ||
dfs(grid, visit, r, c + 1, t) ||
dfs(grid, visit, r, c - 1, t);
}
}
Python
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
visit = [[False] * n for _ in range(n)]
minH = maxH = grid[0][0]
for row in range(n):
maxH = max(maxH, max(grid[row]))
minH = min(minH, min(grid[row]))
def dfs(node, t):
r, c = node
if (min(r, c) < 0 or max(r, c) >= n or
visit[r][c] or grid[r][c] > t):
return False
if r == (n - 1) and c == (n - 1):
return True
visit[r][c] = True
return (dfs((r + 1, c), t) or
dfs((r - 1, c), t) or
dfs((r, c + 1), t) or
dfs((r, c - 1), t))
for t in range(minH, maxH):
if dfs((0, 0), t):
return t
for r in range(n):
for c in range(n):
visit[r][c] = False
return maxH
JavaScript
class Solution {
/**
* @param {number[][]} grid
* @return {number}
*/
swimInWater(grid) {
const n = grid.length;
const visit = Array.from({ length: n }, () =>
Array(n).fill(false));
let minH = grid[0][0], maxH = grid[0][0];
for (let row = 0; row < n; row++) {
for (let col = 0; col < n; col++) {
maxH = Math.max(maxH, grid[row][col]);
minH = Math.min(minH, grid[row][col]);
}
}
const dfs = (node, t) => {
const [r, c] = node;
if (Math.min(r, c) < 0 || Math.max(r, c) >= n ||
visit[r][c] || grid[r][c] > t) {
return false;
}
if (r === n - 1 && c === n - 1) {
return true;
}
visit[r][c] = true;
return dfs([r + 1, c], t) ||
dfs([r - 1, c], t) ||
dfs([r, c + 1], t) ||
dfs([r, c - 1], t);
};
for (let t = minH; t < maxH; t++) {
if (dfs([0, 0], t)) {
return t;
}
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
visit[r][c] = false;
}
}
}
return maxH;
}
}
3. Binary Search + DFS
Use binary search to determine the smallest possible elevation that allows you to reach the destination. For each mid-value, use DFS to check if a path exists within that elevation constraint.
- Time complexity: O(n^{2}log n)
- Space complexity:
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
int swimInWater(vector>& grid) {
int n = grid.size();
vector> visit(n, vector(n, false));
int minH = grid[0][0], maxH = grid[0][0];
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
maxH = max(maxH, grid[row][col]);
minH = min(minH, grid[row][col]);
}
}
int l = minH, r = maxH;
while (l < r) {
int m = (l + r) >> 1;
if (dfs(grid, visit, 0, 0, m)) {
r = m;
} else {
l = m + 1;
}
for (int row = 0; row < n; row++) {
fill(visit[row].begin(), visit[row].end(), false);
}
}
return r;
}
private:
bool dfs(vector>& grid, vector>& visit,
int r, int c, int t) {
if (r < 0 || c < 0 || r >= grid.size() ||
c >= grid.size() || visit[r][c] || grid[r][c] > t) {
return false;
}
if (r == grid.size() - 1 && c == grid.size() - 1) {
return true;
}
visit[r][c] = true;
return dfs(grid, visit, r + 1, c, t) ||
dfs(grid, visit, r - 1, c, t) ||
dfs(grid, visit, r, c + 1, t) ||
dfs(grid, visit, r, c - 1, t);
}
};
Java
public class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
boolean[][] visit = new boolean[n][n];
int minH = grid[0][0], maxH = grid[0][0];
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
maxH = Math.max(maxH, grid[row][col]);
minH = Math.min(minH, grid[row][col]);
}
}
int l = minH, r = maxH;
while (l < r) {
int m = (l + r) >> 1;
if (dfs(grid, visit, 0, 0, m)) {
r = m;
} else {
l = m + 1;
}
for (int row = 0; row < n; row++) {
Arrays.fill(visit[row], false);
}
}
return r;
}
private boolean dfs(int[][] grid, boolean[][] visit, int r, int c, int t) {
if (r < 0 || c < 0 || r >= grid.length ||
c >= grid.length || visit[r][c] || grid[r][c] > t) {
return false;
}
if (r == grid.length - 1 && c == grid.length - 1) {
return true;
}
visit[r][c] = true;
return dfs(grid, visit, r + 1, c, t) ||
dfs(grid, visit, r - 1, c, t) ||
dfs(grid, visit, r, c + 1, t) ||
dfs(grid, visit, r, c - 1, t);
}
}
Python
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
visit = [[False] * n for _ in range(n)]
minH = maxH = grid[0][0]
for row in range(n):
maxH = max(maxH, max(grid[row]))
minH = min(minH, min(grid[row]))
def dfs(node, t):
r, c = node
if (min(r, c) < 0 or max(r, c) >= n or
visit[r][c] or grid[r][c] > t):
return False
if r == (n - 1) and c == (n - 1):
return True
visit[r][c] = True
return (dfs((r + 1, c), t) or
dfs((r - 1, c), t) or
dfs((r, c + 1), t) or
dfs((r, c - 1), t))
l, r = minH, maxH
while l < r:
m = (l + r) >> 1
if dfs((0, 0), m):
r = m
else:
l = m + 1
for row in range(n):
for col in range(n):
visit[row][col] = False
return r
JavaScript
class Solution {
/**
* @param {number[][]} grid
* @return {number}
*/
swimInWater(grid) {
const n = grid.length;
const visit = Array.from({ length: n }, () =>
Array(n).fill(false));
let minH = grid[0][0], maxH = grid[0][0];
for (let row = 0; row < n; row++) {
for (let col = 0; col < n; col++) {
maxH = Math.max(maxH, grid[row][col]);
minH = Math.min(minH, grid[row][col]);
}
}
const dfs = (node, t) => {
const [r, c] = node;
if (Math.min(r, c) < 0 || Math.max(r, c) >= n ||
visit[r][c] || grid[r][c] > t) {
return false;
}
if (r === n - 1 && c === n - 1) {
return true;
}
visit[r][c] = true;
return dfs([r + 1, c], t) ||
dfs([r - 1, c], t) ||
dfs([r, c + 1], t) ||
dfs([r, c - 1], t);
};
let l = minH, r = maxH;
while (l < r) {
let m = (l + r) >> 1;
if (dfs([0, 0], m)) {
r = m;
} else {
l = m + 1;
}
for (let row = 0; row < n; row++) {
for (let col = 0; col < n; col++) {
visit[row][col] = false;
}
}
}
return r;
}
}
4. Dijkstra’s Algorithm
Treat the grid as a weighted graph where elevation acts as the cost. Use a Min-Heap to find the path from the top-left to the bottom-right that minimizes the highest elevation encountered.
- Time complexity: O(n^{2}log n)
- Space complexity: O(n^2)
Code:
C++
Java
Python
JavaScript
C++
class DSU {
vector Parent, Size;
public:
DSU(int n) : Parent(n + 1), Size(n + 1, 1) {
for (int i = 0; i <= n; i++) Parent[i] = i;
}
int find(int node) {
if (Parent[node] != node)
Parent[node] = find(Parent[node]);
return Parent[node];
}
bool unionSets(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (Size[pu] < Size[pv]) swap(pu, pv);
Size[pu] += Size[pv];
Parent[pv] = pu;
return true;
}
bool connected(int u, int v) {
return find(u) == find(v);
}
};
class Solution {
public:
int swimInWater(vector>& grid) {
int N = grid.size();
DSU dsu(N * N);
vector> positions;
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
positions.emplace_back(grid[r][c], r, c);
sort(positions.begin(), positions.end());
vector> directions = {
{0, 1}, {1, 0}, {0, -1}, {-1, 0}
};
for (auto& [t, r, c] : positions) {
for (auto& [dr, dc] : directions) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < N && nc >= 0 &&
nc < N && grid[nr][nc] <= t) {
dsu.unionSets(r * N + c, nr * N + nc);
}
}
if (dsu.connected(0, N * N - 1)) return t;
}
return N * N;
}
};
Java
public class DSU {
private int[] Parent;
private int[] Size;
public DSU(int n) {
Parent = new int[n + 1];
Size = new int[n + 1];
for (int i = 0; i <= n; i++) Parent[i] = i;
Arrays.fill(Size, 1);
}
public int find(int node) {
if (Parent[node] != node)
Parent[node] = find(Parent[node]);
return Parent[node];
}
public boolean union(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (Size[pu] < Size[pv]) {
int temp = pu;
pu = pv;
pv = temp;
}
Size[pu] += Size[pv];
Parent[pv] = pu;
return true;
}
public boolean connected(int u, int v) {
return find(u) == find(v);
}
}
public class Solution {
public int swimInWater(int[][] grid) {
int N = grid.length;
DSU dsu = new DSU(N * N);
List positions = new ArrayList<>();
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
positions.add(new int[]{grid[r][c], r, c});
positions.sort(Comparator.comparingInt(a -> a[0]));
int[][] directions = {
{0, 1}, {1, 0}, {0, -1}, {-1, 0}
};
for (int[] pos : positions) {
int t = pos[0], r = pos[1], c = pos[2];
for (int[] dir : directions) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nr < N && nc >= 0 &&
nc < N && grid[nr][nc] <= t) {
dsu.union(r * N + c, nr * N + nc);
}
}
if (dsu.connected(0, N * N - 1)) return t;
}
return N * N;
}
}
Python
class DSU:
def __init__(self, n):
self.Parent = list(range(n + 1))
self.Size = [1] * (n + 1)
def find(self, node):
if self.Parent[node] != node:
self.Parent[node] = self.find(self.Parent[node])
return self.Parent[node]
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu == pv:
return False
if self.Size[pu] < self.Size[pv]:
pu, pv = pv, pu
self.Size[pu] += self.Size[pv]
self.Parent[pv] = pu
return True
def connected(self, u, v):
return self.find(u) == self.find(v)
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
N = len(grid)
dsu = DSU(N * N)
positions = sorted((grid[r][c], r, c) for r in range(N) for c in range(N))
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for t, r, c in positions:
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N and grid[nr][nc] <= t:
dsu.union(r * N + c, nr * N + nc)
if dsu.connected(0, N * N - 1):
return t
JavaScript
class DSU {
constructor(n) {
this.Parent = Array.from({ length: n + 1 }, (_, i) => i);
this.Size = Array(n + 1).fill(1);
}
/**
* @param {number} node
* @return {number}
*/
find(node) {
if (this.Parent[node] !== node) {
this.Parent[node] = this.find(this.Parent[node]);
}
return this.Parent[node];
}
/**
* @param {number} u
* @param {number} v
* @return {boolean}
*/
union(u, v) {
let pu = this.find(u), pv = this.find(v);
if (pu === pv) return false;
if (this.Size[pu] < this.Size[pv]) [pu, pv] = [pv, pu];
this.Size[pu] += this.Size[pv];
this.Parent[pv] = pu;
return true;
}
/**
* @param {number} n
* @param {number} n
* @return {boolean}
*/
connected(u, v) {
return this.find(u) == this.find(v);
}
}
class Solution {
/**
* @param {number[][]} grid
* @return {number}
*/
swimInWater(grid) {
const N = grid.length;
const dsu = new DSU(N * N);
const positions = [];
for (let r = 0; r < N; r++) {
for (let c = 0; c < N; c++) {
positions.push([grid[r][c], r, c]);
}
}
positions.sort((a, b) => a[0] - b[0]);
const directions = [
[0, 1], [1, 0], [0, -1], [-1, 0]
];
for (const [t, r, c] of positions) {
for (const [dr, dc] of directions) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < N && nc >= 0 &&
nc < N && grid[nr][nc] <= t) {
dsu.union(r * N + c, nr * N + nc);
}
}
if (dsu.connected(0, N * N - 1)) return t;
}
return N * N;
}
}
5. Kruskal’s Algorithm
View the problem as finding a Minimum Spanning Tree (MST) over the grid. Use Kruskal’s algorithm to connect nodes (cells) with edges weighted by elevation, ensuring all nodes are connected with minimal maximum elevation.
- Time complexity: O(n^{2}log n)
- Space complexity: O(n^{2})
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
int networkDelayTime(vector>& times, int n, int k) {
unordered_map>> edges;
for (const auto& time : times) {
edges[time[0]].emplace_back(time[1], time[2]);
}
priority_queue, vector>, greater<>> minHeap;
minHeap.push({0, k});
set visited;
int t = 0;
while (!minHeap.empty()) {
auto curr = minHeap.top();
minHeap.pop();
int w1 = curr.first, n1 = curr.second;
if (visited.count(n1)) {
continue;
}
visited.insert(n1);
t = w1;
if (edges.count(n1)) {
for (const auto& next : edges[n1]) {
int n2 = next.first, w2 = next.second;
if (!visited.count(n2)) {
minHeap.push({w1 + w2, n2});
}
}
}
}
return visited.size() == n ? t : -1;
}
};
Java
public class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map> edges = new HashMap<>();
for (int[] time : times) {
edges.computeIfAbsent(time[0],
key -> new ArrayList<>()).add(new int[]{time[1], time[2]});
}
PriorityQueue minHeap = new PriorityQueue<>(
Comparator.comparingInt(a -> a[0]));
minHeap.offer(new int[]{0, k});
Set visited = new HashSet<>();
int t = 0;
while (!minHeap.isEmpty()) {
int[] curr = minHeap.poll();
int w1 = curr[0], n1 = curr[1];
if (visited.contains(n1)) {
continue;
}
visited.add(n1);
t = w1;
if (edges.containsKey(n1)) {
for (int[] next : edges.get(n1)) {
int n2 = next[0], w2 = next[1];
if (!visited.contains(n2)) {
minHeap.offer(new int[]{w1 + w2, n2});
}
}
}
}
return visited.size() == n ? t : -1;
}
}
Python
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
edges = collections.defaultdict(list)
for u, v, w in times:
edges[u].append((v, w))
minHeap = [(0, k)]
visit = set()
t = 0
while minHeap:
w1, n1 = heapq.heappop(minHeap)
if n1 in visit:
continue
visit.add(n1)
t = w1
for n2, w2 in edges[n1]:
if n2 not in visit:
heapq.heappush(minHeap, (w1 + w2, n2))
return t if len(visit) == n else -1
JavaScript
/**
* const { MinPriorityQueue } = require('@datastructures-js/priority-queue');
*/
class Solution {
/**
* @param {number[][]} times
* @param {number} n
* @param {number} k
* @return {number}
*/
networkDelayTime(times, n, k) {
const edges = new Map();
for (let i = 1; i <= n; i++) {
edges.set(i, []);
}
for (const [u, v, w] of times) {
edges.get(u).push([v, w]);
}
const minHeap = new MinPriorityQueue(entry => entry[0]);
minHeap.enqueue([0, k]);
const visit = new Set();
let t = 0;
while (!minHeap.isEmpty()) {
const [w1, n1] = minHeap.dequeue();
if (visit.has(n1)) continue;
visit.add(n1);
t = w1;
for (const [n2, w2] of edges.get(n1)) {
if (!visit.has(n2)) {
minHeap.enqueue([w1 + w2, n2]);
}
}
}
return visit.size === n ? t : -1;
}
}
