给定一个由 N 个节点和 E 条边组成的图，边的形式为 {U, V, W}，表示 U 和 V 之间存在一条权重为 W 的边。现在给定一个整数 K 以及起点 src 和终点 dst。我们的任务是找到从起点到终点，且经停次数不超过 K 次的最便宜路径。
示例：
> 输入： N = 3, edges = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 1
> 输出： 200
> 解释：
> 从城市 0 到城市 2 的最便宜价格是 200。在只经停一次的情况下，正好花费 200，这就是我们的输出结果。
> 输入： N = 3, edges = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 0
> 输出： 500
方法 1：使用 深度优先搜索
在这个方法中，我们将采取以下步骤：
- 探索当前节点，并持续探索其子节点。
- 使用一个 映射来存储已访问的节点，并将经停次数和距离作为值配对存储。
- 如果映射中存在当前键，则中断递归树（剪枝）。
- 找出每个递归树的答案（即最小成本）并返回。
下面是我们这种方法的实现。
C++
CODEBLOCK_c3e2af12
Java
`
// Java program for the above approach
import java.util.HashMap;
public class SingleS {
// DFS memoization
static int adjMatrix[][];
static HashMap mp
= new HashMap();
// Function to implement DFS Traversal
static int DFSUtility(int node, int stops, int dst,
int cities)
{
// Base Case
if (node == dst)
return 0;
if (stops < 0)
return Integer.MAX_VALUE;
int[] key = new int[] { node, stops };
// Find value with key in a map
if (mp.containsKey(key))
return mp.get(mp);
int ans = Integer.MAX_VALUE;
// Traverse adjacency matrix of
// source node
for (int neighbour = 0; neighbour 0) {
// Recursive DFS call for
// child node