bowang0911/leetcode huggingface dataset:
Couples Holding Hands

There are `n` couples sitting in `2n` seats arranged in a row and want to hold hands.

The people and seats are represented by an integer array `row` where `row[i]` is the ID of the person sitting in the `ith` seat. The couples are numbered in order, the first couple being `(0, 1)`, the second couple being `(2, 3)`, and so on with the last couple being `(2n - 2, 2n - 1)`.

Return _the minimum number of swaps so that every couple is sitting side by side_. A swap consists of choosing any two people, then they stand up and switch seats.

**Example 1:**

**Input:** row = \[0,2,1,3\]
**Output:** 1
**Explanation:** We only need to swap the second (row\[1\]) and third (row\[2\]) person.

**Example 2:**

**Input:** row = \[3,2,0,1\]
**Output:** 0
**Explanation:** All couples are already seated side by side.

**Constraints:**

*   `2n == row.length`
*   `2 <= n <= 30`
*   `n` is even.
*   `0 <= row[i] < 2n`
*   All the elements of `row` are **unique**.
Toeplitz Matrix

Given an `m x n` `matrix`, return _`true` if the matrix is Toeplitz. Otherwise, return `false`._

A matrix is **Toeplitz** if every diagonal from top-left to bottom-right has the same elements.

**Example 1:**

**Input:** matrix = \[\[1,2,3,4\],\[5,1,2,3\],\[9,5,1,2\]\]
**Output:** true
**Explanation:**
In the above grid, the diagonals are:
 "\[9\] ",  "\[5, 5\] ",  "\[1, 1, 1\] ",  "\[2, 2, 2\] ",  "\[3, 3\] ",  "\[4\] ".
In each diagonal all elements are the same, so the answer is True.

**Example 2:**

**Input:** matrix = \[\[1,2\],\[2,2\]\]
**Output:** false
**Explanation:**
The diagonal  "\[1, 2\] " has different elements.

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 20`
*   `0 <= matrix[i][j] <= 99`

**Follow up:**

*   What if the `matrix` is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
*   What if the `matrix` is so large that you can only load up a partial row into the memory at once?
Reorganize String

Given a string `s`, rearrange the characters of `s` so that any two adjacent characters are not the same.

Return _any possible rearrangement of_ `s` _or return_ `" "` _if not possible_.

**Example 1:**

**Input:** s = "aab"
**Output:** "aba"

**Example 2:**

**Input:** s = "aaab"
**Output:** ""

**Constraints:**

*   `1 <= s.length <= 500`
*   `s` consists of lowercase English letters.
Max Chunks To Make Sorted II

You are given an integer array `arr`.

We split `arr` into some number of **chunks** (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return _the largest number of chunks we can make to sort the array_.

**Example 1:**

**Input:** arr = \[5,4,3,2,1\]
**Output:** 1
**Explanation:**
Splitting into two or more chunks will not return the required result.
For example, splitting into \[5, 4\], \[3, 2, 1\] will result in \[4, 5, 1, 2, 3\], which isn't sorted.

**Example 2:**

**Input:** arr = \[2,1,3,4,4\]
**Output:** 4
**Explanation:**
We can split into two chunks, such as \[2, 1\], \[3, 4, 4\].
However, splitting into \[2, 1\], \[3\], \[4\], \[4\] is the highest number of chunks possible.

**Constraints:**

*   `1 <= arr.length <= 2000`
*   `0 <= arr[i] <= 108`
Max Chunks To Make Sorted

You are given an integer array `arr` of length `n` that represents a permutation of the integers in the range `[0, n - 1]`.

We split `arr` into some number of **chunks** (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return _the largest number of chunks we can make to sort the array_.

**Example 1:**

**Input:** arr = \[4,3,2,1,0\]
**Output:** 1
**Explanation:**
Splitting into two or more chunks will not return the required result.
For example, splitting into \[4, 3\], \[2, 1, 0\] will result in \[3, 4, 0, 1, 2\], which isn't sorted.

**Example 2:**

**Input:** arr = \[1,0,2,3,4\]
**Output:** 4
**Explanation:**
We can split into two chunks, such as \[1, 0\], \[2, 3, 4\].
However, splitting into \[1, 0\], \[2\], \[3\], \[4\] is the highest number of chunks possible.

**Constraints:**

*   `n == arr.length`
*   `1 <= n <= 10`
*   `0 <= arr[i] < n`
*   All the elements of `arr` are **unique**.
Basic Calculator IV

Given an expression such as `expression = "e + 8 - a + 5 "` and an evaluation map such as `{ "e ": 1}` (given in terms of `evalvars = [ "e "]` and `evalints = [1]`), return a list of tokens representing the simplified expression, such as `[ "-1*a ", "14 "]`

*   An expression alternates chunks and symbols, with a space separating each chunk and symbol.
*   A chunk is either an expression in parentheses, a variable, or a non-negative integer.
*   A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like `"2x "` or `"-x "`.

Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction.

*   For example, `expression = "1 + 2 * 3 "` has an answer of `[ "7 "]`.

The format of the output is as follows:

*   For each term of free variables with a non-zero coefficient, we write the free variables within a term in sorted order lexicographically.
    *   For example, we would never write a term like `"b*a*c "`, only `"a*b*c "`.
*   Terms have degrees equal to the number of free variables being multiplied, counting multiplicity. We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
    *   For example, `"a*a*b*c "` has degree `4`.
*   The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.) A leading coefficient of 1 is still printed.
*   An example of a well-formatted answer is `[ "-2*a*a*a ", "3*a*a*b ", "3*b*b ", "4*a ", "5*c ", "-6 "]`.
*   Terms (including constant terms) with coefficient `0` are not included.
    *   For example, an expression of `"0 "` has an output of `[]`.

**Note:** You may assume that the given expression is always valid. All intermediate results will be in the range of `[-231, 231 - 1]`.

**Example 1:**

**Input:** expression =  "e + 8 - a + 5 ", evalvars = \[ "e "\], evalints = \[1\]
**Output:** \[ "-1\*a ", "14 "\]

**Example 2:**

**Input:** expression =  "e - 8 + temperature - pressure ", evalvars = \[ "e ",  "temperature "\], evalints = \[1, 12\]
**Output:** \[ "-1\*pressure ", "5 "\]

**Example 3:**

**Input:** expression =  "(e + 8) \* (e - 8) ", evalvars = \[\], evalints = \[\]
**Output:** \[ "1\*e\*e ", "-64 "\]

**Constraints:**

*   `1 <= expression.length <= 250`
*   `expression` consists of lowercase English letters, digits, `'+'`, `'-'`, `'*'`, `'('`, `')'`, `' '`.
*   `expression` does not contain any leading or trailing spaces.
*   All the tokens in `expression` are separated by a single space.
*   `0 <= evalvars.length <= 100`
*   `1 <= evalvars[i].length <= 20`
*   `evalvars[i]` consists of lowercase English letters.
*   `evalints.length == evalvars.length`
*   `-100 <= evalints[i] <= 100`
Jewels and Stones

You're given strings `jewels` representing the types of stones that are jewels, and `stones` representing the stones you have. Each character in `stones` is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so `"a "` is considered a different type of stone from `"A "`.

**Example 1:**

**Input:** jewels = "aA", stones = "aAAbbbb"
**Output:** 3

**Example 2:**

**Input:** jewels = "z", stones = "ZZ"
**Output:** 0

**Constraints:**

*   `1 <= jewels.length, stones.length <= 50`
*   `jewels` and `stones` consist of only English letters.
*   All the characters of `jewels` are **unique**.
Basic Calculator III

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, `'+'`, `'-'`, `'*'`, `'/'` operators, and open `'('` and closing parentheses `')'`. The integer division should **truncate toward zero**.

You may assume that the given expression is always valid. All intermediate results will be in the range of `[-231, 231 - 1]`.

**Note:** You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as `eval()`.

**Example 1:**

**Input:** s =  "1+1 "
**Output:** 2

**Example 2:**

**Input:** s =  "6-4/2 "
**Output:** 4

**Example 3:**

**Input:** s =  "2\*(5+5\*2)/3+(6/2+8) "
**Output:** 21

**Constraints:**

*   `1 <= s <= 104`
*   `s` consists of digits, `'+'`, `'-'`, `'*'`, `'/'`, `'('`, and `')'`.
*   `s` is a **valid** expression.
Sliding Puzzle

On an `2 x 3` board, there are five tiles labeled from `1` to `5`, and an empty square represented by `0`. A **move** consists of choosing `0` and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is `[[1,2,3],[4,5,0]]`.

Given the puzzle board `board`, return _the least number of moves required so that the state of the board is solved_. If it is impossible for the state of the board to be solved, return `-1`.

**Example 1:**

**Input:** board = \[\[1,2,3\],\[4,0,5\]\]
**Output:** 1
**Explanation:** Swap the 0 and the 5 in one move.

**Example 2:**

**Input:** board = \[\[1,2,3\],\[5,4,0\]\]
**Output:** -1
**Explanation:** No number of moves will make the board solved.

**Example 3:**

**Input:** board = \[\[4,1,2\],\[5,0,3\]\]
**Output:** 5
**Explanation:** 5 is the smallest number of moves that solves the board.
An example path:
After move 0: \[\[4,1,2\],\[5,0,3\]\]
After move 1: \[\[4,1,2\],\[0,5,3\]\]
After move 2: \[\[0,1,2\],\[4,5,3\]\]
After move 3: \[\[1,0,2\],\[4,5,3\]\]
After move 4: \[\[1,2,0\],\[4,5,3\]\]
After move 5: \[\[1,2,3\],\[4,5,0\]\]

**Constraints:**

*   `board.length == 2`
*   `board[i].length == 3`
*   `0 <= board[i][j] <= 5`
*   Each value `board[i][j]` is **unique**.
Minimize Max Distance to Gas Station

You are given an integer array `stations` that represents the positions of the gas stations on the **x-axis**. You are also given an integer `k`.

You should add `k` new gas stations. You can add the stations anywhere on the **x-axis**, and not necessarily on an integer position.

Let `penalty()` be the maximum distance between **adjacent** gas stations after adding the `k` new stations.

Return _the smallest possible value of_ `penalty()`. Answers within `10-6` of the actual answer will be accepted.

**Example 1:**

**Input:** stations = \[1,2,3,4,5,6,7,8,9,10\], k = 9
**Output:** 0.50000

**Example 2:**

**Input:** stations = \[23,24,36,39,46,56,57,65,84,98\], k = 1
**Output:** 14.00000

**Constraints:**

*   `10 <= stations.length <= 2000`
*   `0 <= stations[i] <= 108`
*   `stations` is sorted in a **strictly increasing** order.
*   `1 <= k <= 106`
Global and Local Inversions

You are given an integer array `nums` of length `n` which represents a permutation of all the integers in the range `[0, n - 1]`.

The number of **global inversions** is the number of the different pairs `(i, j)` where:

*   `0 <= i < j < n`
*   `nums[i] > nums[j]`

The number of **local inversions** is the number of indices `i` where:

*   `0 <= i < n - 1`
*   `nums[i] > nums[i + 1]`

Return `true` _if the number of **global inversions** is equal to the number of **local inversions**_.

**Example 1:**

**Input:** nums = \[1,0,2\]
**Output:** true
**Explanation:** There is 1 global inversion and 1 local inversion.

**Example 2:**

**Input:** nums = \[1,2,0\]
**Output:** false
**Explanation:** There are 2 global inversions and 1 local inversion.

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 105`
*   `0 <= nums[i] < n`
*   All the integers of `nums` are **unique**.
*   `nums` is a permutation of all the numbers in the range `[0, n - 1]`.
Split BST

Given the `root` of a binary search tree (BST) and an integer `target`, split the tree into two subtrees where one subtree has nodes that are all smaller or equal to the target value, while the other subtree has all nodes that are greater than the target value. It Is not necessarily the case that the tree contains a node with the value `target`.

Additionally, most of the structure of the original tree should remain. Formally, for any child `c` with parent `p` in the original tree, if they are both in the same subtree after the split, then node `c` should still have the parent `p`.

Return _an array of the two roots of the two subtrees_.

**Example 1:**

**Input:** root = \[4,2,6,1,3,5,7\], target = 2
**Output:** \[\[2,1\],\[4,3,6,null,null,5,7\]\]

**Example 2:**

**Input:** root = \[1\], target = 1
**Output:** \[\[1\],\[\]\]

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 50]`.
*   `0 <= Node.val, target <= 1000`
Swap Adjacent in LR String

In a string composed of `'L'`, `'R'`, and `'X'` characters, like `"RXXLRXRXL "`, a move consists of either replacing one occurrence of `"XL "` with `"LX "`, or replacing one occurrence of `"RX "` with `"XR "`. Given the starting string `start` and the ending string `end`, return `True` if and only if there exists a sequence of moves to transform one string to the other.

**Example 1:**

**Input:** start =  "RXXLRXRXL ", end =  "XRLXXRRLX "
**Output:** true
**Explanation:** We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

**Example 2:**

**Input:** start =  "X ", end =  "L "
**Output:** false

**Constraints:**

*   `1 <= start.length <= 104`
*   `start.length == end.length`
*   Both `start` and `end` will only consist of characters in `'L'`, `'R'`, and `'X'`.
Swim in Rising Water

You are given an `n x n` integer matrix `grid` where each value `grid[i][j]` represents the elevation at that point `(i, j)`.

The rain starts to fall. At time `t`, the depth of the water everywhere is `t`. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most `t`. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return _the least time until you can reach the bottom right square_ `(n - 1, n - 1)` _if you start at the top left square_ `(0, 0)`.

**Example 1:**

**Input:** grid = \[\[0,2\],\[1,3\]\]
**Output:** 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

**Example 2:**

**Input:** grid = \[\[0,1,2,3,4\],\[24,23,22,21,5\],\[12,13,14,15,16\],\[11,17,18,19,20\],\[10,9,8,7,6\]\]
**Output:** 16
**Explanation:** The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

**Constraints:**

*   `n == grid.length`
*   `n == grid[i].length`
*   `1 <= n <= 50`
*   `0 <= grid[i][j] < n2`
*   Each value `grid[i][j]` is **unique**.
K-th Symbol in Grammar

We build a table of `n` rows (**1-indexed**). We start by writing `0` in the `1st` row. Now in every subsequent row, we look at the previous row and replace each occurrence of `0` with `01`, and each occurrence of `1` with `10`.

*   For example, for `n = 3`, the `1st` row is `0`, the `2nd` row is `01`, and the `3rd` row is `0110`.

Given two integer `n` and `k`, return the `kth` (**1-indexed**) symbol in the `nth` row of a table of `n` rows.

**Example 1:**

**Input:** n = 1, k = 1
**Output:** 0
**Explanation:** row 1: 0

**Example 2:**

**Input:** n = 2, k = 1
**Output:** 0
**Explanation:** 
row 1: 0
row 2: 01

**Example 3:**

**Input:** n = 2, k = 2
**Output:** 1
**Explanation:** 
row 1: 0
row 2: 01

**Constraints:**

*   `1 <= n <= 30`
*   `1 <= k <= 2n - 1`
Reaching Points

Given four integers `sx`, `sy`, `tx`, and `ty`, return `true` _if it is possible to convert the point_ `(sx, sy)` _to the point_ `(tx, ty)` _through some operations__, or_ `false` _otherwise_.

The allowed operation on some point `(x, y)` is to convert it to either `(x, x + y)` or `(x + y, y)`.

**Example 1:**

**Input:** sx = 1, sy = 1, tx = 3, ty = 5
**Output:** true
**Explanation:**
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

**Example 2:**

**Input:** sx = 1, sy = 1, tx = 2, ty = 2
**Output:** false

**Example 3:**

**Input:** sx = 1, sy = 1, tx = 1, ty = 1
**Output:** true

**Constraints:**

*   `1 <= sx, sy, tx, ty <= 109`
Rabbits in Forest

There is a forest with an unknown number of rabbits. We asked n rabbits **"How many rabbits have the same color as you? "** and collected the answers in an integer array `answers` where `answers[i]` is the answer of the `ith` rabbit.

Given the array `answers`, return _the minimum number of rabbits that could be in the forest_.

**Example 1:**

**Input:** answers = \[1,1,2\]
**Output:** 5
**Explanation:**
The two rabbits that answered  "1 " could both be the same color, say red.
The rabbit that answered  "2 " can't be red or the answers would be inconsistent.
Say the rabbit that answered  "2 " was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

**Example 2:**

**Input:** answers = \[10,10,10\]
**Output:** 11

**Constraints:**

*   `1 <= answers.length <= 1000`
*   `0 <= answers[i] < 1000`
Transform to Chessboard

You are given an `n x n` binary grid `board`. In each move, you can swap any two rows with each other, or any two columns with each other.

Return _the minimum number of moves to transform the board into a **chessboard board**_. If the task is impossible, return `-1`.

A **chessboard board** is a board where no `0`'s and no `1`'s are 4-directionally adjacent.

**Example 1:**

**Input:** board = \[\[0,1,1,0\],\[0,1,1,0\],\[1,0,0,1\],\[1,0,0,1\]\]
**Output:** 2
**Explanation:** One potential sequence of moves is shown.
The first move swaps the first and second column.
The second move swaps the second and third row.

**Example 2:**

**Input:** board = \[\[0,1\],\[1,0\]\]
**Output:** 0
**Explanation:** Also note that the board with 0 in the top left corner, is also a valid chessboard.

**Example 3:**

**Input:** board = \[\[1,0\],\[1,0\]\]
**Output:** -1
**Explanation:** No matter what sequence of moves you make, you cannot end with a valid chessboard.

**Constraints:**

*   `n == board.length`
*   `n == board[i].length`
*   `2 <= n <= 30`
*   `board[i][j]` is either `0` or `1`.
Minimum Distance Between BST Nodes

Given the `root` of a Binary Search Tree (BST), return _the minimum difference between the values of any two different nodes in the tree_.

**Example 1:**

**Input:** root = \[4,2,6,1,3\]
**Output:** 1

**Example 2:**

**Input:** root = \[1,0,48,null,null,12,49\]
**Output:** 1

**Constraints:**

*   The number of nodes in the tree is in the range `[2, 100]`.
*   `0 <= Node.val <= 105`

**Note:** This question is the same as 530: [https://leetcode.com/problems/minimum-absolute-difference-in-bst/](https://leetcode.com/problems/minimum-absolute-difference-in-bst/)
Letter Case Permutation

Given a string `s`, you can transform every letter individually to be lowercase or uppercase to create another string.

Return _a list of all possible strings we could create_. Return the output in **any order**.

**Example 1:**

**Input:** s =  "a1b2 "
**Output:** \[ "a1b2 ", "a1B2 ", "A1b2 ", "A1B2 "\]

**Example 2:**

**Input:** s =  "3z4 "
**Output:** \[ "3z4 ", "3Z4 "\]

**Constraints:**

*   `1 <= s.length <= 12`
*   `s` consists of lowercase English letters, uppercase English letters, and digits.
Is Graph Bipartite?

There is an **undirected** graph with `n` nodes, where each node is numbered between `0` and `n - 1`. You are given a 2D array `graph`, where `graph[u]` is an array of nodes that node `u` is adjacent to. More formally, for each `v` in `graph[u]`, there is an undirected edge between node `u` and node `v`. The graph has the following properties:

*   There are no self-edges (`graph[u]` does not contain `u`).
*   There are no parallel edges (`graph[u]` does not contain duplicate values).
*   If `v` is in `graph[u]`, then `u` is in `graph[v]` (the graph is undirected).
*   The graph may not be connected, meaning there may be two nodes `u` and `v` such that there is no path between them.

A graph is **bipartite** if the nodes can be partitioned into two independent sets `A` and `B` such that **every** edge in the graph connects a node in set `A` and a node in set `B`.

Return `true` _if and only if it is **bipartite**_.

**Example 1:**

**Input:** graph = \[\[1,2,3\],\[0,2\],\[0,1,3\],\[0,2\]\]
**Output:** false
**Explanation:** There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

**Example 2:**

**Input:** graph = \[\[1,3\],\[0,2\],\[1,3\],\[0,2\]\]
**Output:** true
**Explanation:** We can partition the nodes into two sets: {0, 2} and {1, 3}.

**Constraints:**

*   `graph.length == n`
*   `1 <= n <= 100`
*   `0 <= graph[u].length < n`
*   `0 <= graph[u][i] <= n - 1`
*   `graph[u]` does not contain `u`.
*   All the values of `graph[u]` are **unique**.
*   If `graph[u]` contains `v`, then `graph[v]` contains `u`.
K-th Smallest Prime Fraction

You are given a sorted integer array `arr` containing `1` and **prime** numbers, where all the integers of `arr` are unique. You are also given an integer `k`.

For every `i` and `j` where `0 <= i < j < arr.length`, we consider the fraction `arr[i] / arr[j]`.

Return _the_ `kth` _smallest fraction considered_. Return your answer as an array of integers of size `2`, where `answer[0] == arr[i]` and `answer[1] == arr[j]`.

**Example 1:**

**Input:** arr = \[1,2,3,5\], k = 3
**Output:** \[2,5\]
**Explanation:** The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

**Example 2:**

**Input:** arr = \[1,7\], k = 1
**Output:** \[1,7\]

**Constraints:**

*   `2 <= arr.length <= 1000`
*   `1 <= arr[i] <= 3 * 104`
*   `arr[0] == 1`
*   `arr[i]` is a **prime** number for `i > 0`.
*   All the numbers of `arr` are **unique** and sorted in **strictly increasing** order.
*   `1 <= k <= arr.length * (arr.length - 1) / 2`

**Follow up:** Can you solve the problem with better than `O(n2)` complexity?
Cheapest Flights Within K Stops

There are `n` cities connected by some number of flights. You are given an array `flights` where `flights[i] = [fromi, toi, pricei]` indicates that there is a flight from city `fromi` to city `toi` with cost `pricei`.

You are also given three integers `src`, `dst`, and `k`, return _**the cheapest price** from_ `src` _to_ `dst` _with at most_ `k` _stops._ If there is no such route, return `-1`.

**Example 1:**

**Input:** n = 4, flights = \[\[0,1,100\],\[1,2,100\],\[2,0,100\],\[1,3,600\],\[2,3,200\]\], src = 0, dst = 3, k = 1
**Output:** 700
**Explanation:**
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities \[0,1,2,3\] is cheaper but is invalid because it uses 2 stops.

**Example 2:**

**Input:** n = 3, flights = \[\[0,1,100\],\[1,2,100\],\[0,2,500\]\], src = 0, dst = 2, k = 1
**Output:** 200
**Explanation:**
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

**Example 3:**

**Input:** n = 3, flights = \[\[0,1,100\],\[1,2,100\],\[0,2,500\]\], src = 0, dst = 2, k = 0
**Output:** 500
**Explanation:**
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

**Constraints:**

*   `1 <= n <= 100`
*   `0 <= flights.length <= (n * (n - 1) / 2)`
*   `flights[i].length == 3`
*   `0 <= fromi, toi < n`
*   `fromi != toi`
*   `1 <= pricei <= 104`
*   There will not be any multiple flights between two cities.
*   `0 <= src, dst, k < n`
*   `src != dst`