第十四届蓝桥杯省赛真题 Java B 组【原卷】

文章目录

发现宝藏
【考生须知】
试题 A: 阶乘求和
试题 B: 幸运数字
试题 C: 数组分割
试题 D: 矩形总面积
试题 E: 蜗牛
试题 F: 合并区域
试题 $\mathrm{G}:$ 买二赠一
试题 $\mathrm{H}$ : 合并石子
试题 I：最大开支
试题 $\mathrm{J}:$ 魔法阵

发现宝藏

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。【宝藏入口】。

第十四届蓝桥杯大赛软件赛省赛 Java 大学 B 组

【考生须知】

考试开始后, 选手首先下戟题日, 并使用考场现场公布的解压密码解压试题。

考试时间为 4 小时。考试期间选手可浏览白已已经提交的答案, 被浏览的答案允许拷贝。时间截止后, 将无法继续提交或浏览答案。

对同一题目, 选手可多次提交答案, 以最后一次提交的答案为准。

选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它方式提交的答案无效。

试题包含“结果填空”和“程序设计”两种题型。

结果填空题: 要求选于根据题日描述直接填写结果。求解方式不限。不要求源代码。把结果媜空的答案直接通过网页提交即可, 不要书写多余的内容。

程序设计题: 要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果才有机会得分。

注意: 在评炎时使用的输入数据与试炎中给出的示例数据可能是不同的。迅手的程序必须是通用的, 不能只对试卷中给定的数据有效。

所有源码必须在同一文件中。调试通过后，拷贝提交.

注意: 不要使用 package 语句。

注意: 选手代码的主类名必须为: Main, 否则会被判为无效代码。

注意: 如果程序中引用了类库, 在提交时必须将 import 语句与程序的其他部分同时提交。只允许使用 Java 自带的类库。

试题 A: 阶乘求和

本题总分: 5 分

【问题描述】

令 $!+\ldots+202320232023 !$ , 求 $S$ 的末尾 9 位数字。

提示: 答案首位不为 0 。

【答案提交】

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一

个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

试题 B: 幸运数字

本题总分: 5 分

【问题描述】

哈沙德数是指在某个周定的进位制当中, 可以被各位数字之和整除的正整数。例如 126是十进制下的一个哈沙德数, 因为 $(126)_{10} \bmod (1+2+6)=0 ; 126$ 也是八进制下的哈沙德数, 因为 $(126)_{10}=(176)_{8},(126)_{10} \bmod (1+7+6)=0$ ;同时 126 也是 16 进制下的哈沙德数, 因为 $(126)_{10}=(7 e)_{16},(126)_{10} \bmod (7+$ $e) = 0$ 。小蓝认为, 如果一个整数在二进制、八进制、 1 进制、十六进制下均为哈沙德数, 那么这个数字就足幸运数字, 第 1 至第 10 个幸运数字的 1 进制表示为: $\ldots$ . 现在他照知道第 2023 个幸运数字是多少? 你只需要告诉小蓝这个整数的十进制表示即可。

【答案提交】

这足一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

试题 C: 数组分割

时间限制: $\mathrm{~s}$ 内存限制: $\mathrm{MB}$ 本题总分: 10 分

【问题描述】

小蓝有一个长度为 $N$ 的数组 $A=\left[A_{0}, A_{1}, \ldots, A_{N-1}\right]$ 。现在小蓝想要从 $A$ 对应的数组下标所构成的集合 $I=\{0,1,2, \ldots, N-1\}$ 中找出一个子集 $R_{1}$ , 那么 $R_{1}$ 在 $I$ 中的补集为 $R_{2}$ 。记 $S_{1}=\sum_{r \in R_{1}} A_{r}, S_{2}=\sum_{r \in R_{2}} A_{r}$ , 我们要求 $S_{1}$ 和 $S_{2}$ 均为偶数, 请问在这种情况下共有多少种不同的 $R_{1}$ 。当 $R_{1}$ 或 $R_{2}$ 为空集时我们将 $S_{1}$ 或 $S_{2}$ 视为 0 。

【输入格式】

第一行一个整数 $T$ , 表示有 $T$ 组数据。

接下来输入 $T$ 组数据, 每组数据包含两行: 第一行一个整数 $N$ , 表示数组 $A$ 的长度; 第二行输入 $N$ 个整数从全至有依次为 $A_{0}, A_{1}, \ldots, A_{N-1}$ , 相邻元素之间用空格分隔。

【输出格式】

对于每组数据, 输出一行, 包含一个整数表示答案, 答案可能会很大, 你需要将答案对 1000000007 进行取模后输出。

【样例输入】

$\begin{array}{lll}2\end{array}$
$\begin{array}{lll}2\end{array}$
$\begin{array}{lll}6&6\end{array}$
$\begin{array}{lll}2\end{array}$
$\begin{array}{lll}1&6\end{array}$

【样例输出】

$\begin{array}{lll}4\end{array}$
$\begin{array}{lll}0\end{array}$

【样例说明】

对于第一组数据, 答案为 4 。(注意: 大括号内的数字表示元素在数组中的下标。

$R_{1}=\{0\}, R_{2}=\{1\}$ ; 此时 $S_{1}=A_{0}=6$ 为偶数, $S_{2}=A_{1}=6$ 为偶数。

$R_{1}=\{1\}, R_{2}=\{0\}$ ; 此时 $S_{1}=A_{1}=6$ 为偶数, $S_{2}=A_{0}=6$ 为偶数。

${ } ; R_{1}=\{0,1\}, R_{2}=\{\} ;$ 此时 $S_{1}=A_{0}+A_{1}=12$ 为偶数, $S_{2}=0$ 为偶数。

$R_{1}=\{\}, R_{2}=\{0,1\}:$ 此时 $S_{1}=0$ 为偶数, $S_{2}=A_{0}+A_{1}=12$ 为偶数。

对于第二组数据, 无论怎么选择, 都不满足条件, 所以答案为 0 。

【评测用例规模与约定】

对于 $\%$ 的评测用例, $\leq N \leq 10$ 。

对于 $\%$ 的评测用例, $\leq N \leq 10^{2}$ 。

对于 $\%$ 的评测用例, $\leq T \leq 10,1 \leq N \leq 10^{3}, 0 \leq A_{i} \leq 10^{9}$ 。

试题 D: 矩形总面积

时间限制: $\mathrm{~s}$ 内存限制: $\mathrm{MB}$ 本题总分: 10 分

【问题描述】

平面上有个两个矩形 $R_{1}$ 和 $R_{2}$ , 它们各边都与坐标轴平行。设 $\left(x_{1}, y_{1}\right)$ 和 $\left(x_{2}, y_{2}\right)$ 依次定 $R_{1}$ 的左下角和右上角坐标, $\left(x_{3}, y_{3}\right)$ 和 $\left(x_{4}, y_{4}\right)$ 依次定 $R_{2}$ 的左下角和右上角坐标, 请你计算 $R_{1}$ 和 $R_{2}$ 的总面积是多少?

注意：如果 $R_{1}$ 和 $R_{2}$ 有重叠区域, 重叠区域的面积只计算一次。

【输入格式】

输入只有一行, 包含 8 个整数, 依次定: $x_{1}, y_{1}, x_{2}, y_{2}, x_{3}, y_{3}, x_{4}$ 和 $y_{4}$ 。

【输出格式】

个整数, 代表答案。

【样例输入】

$\begin{array}{llllllll}2 & 1 & 7 & 4 & 5 & 3 & 8 & 6\end{array}$

【样例输出】

$\begin{array}{lll}22\end{array}$

【样例说明】

样例中的两个矩形如图所示:

在这里插入图片描述

【评测用例规模与约定】

对于 $\%$ 的数据, $R_{1}$ 和 $R_{2}$ 没有重叠区域。

对于 $\%$ 的数据, 其中一个矩形完全在另一个矩形内部。

对于 $\%$ 的数据, 所有坐标的取值范围是 $\left[0,10^{3}\right]$ 。

对于 $\%$ 的数据, 所有坐标的取值范围足 $\left[0,10^{5}\right]$ 。

试题 E: 蜗牛

时间限制: $\mathrm{~s}$ 内存限制: $\mathrm{MB}$ 本题总分: 15 分

【问题描述】

这天, 一只蜗牛来到了二维坐标系的原点。

在 $x$ 轴上长有 $n$ 根竹䇢。它们平行于 $y$ 轴, 底部纵坐标为 0 , 横坐标分别为 $x_{1}, x_{2}, \ldots, x_{n}$ 。竹竿的高度均为无限高, 宽度可忽略。蜗牛想要从原点走到第 $n$ 个竹篎的底部也就足坐标 $\left(x_{n}, 0\right)$ 。它只能在 $x$ 轴上或者竹竿上爬行, 在 $x$ 轴上爬行速度为 1 单位每秒; 由于受到引力影响, 蜗牛在竹竿上向上和向下爬行的速度分别为 0.7 单位每秒和 1.3 单位每秒。

为了快速到达目的地, 它施展了悗法, 在第 $i$ 和 $i + 1$ 根竹等之间建立了传送门 $(0 < i < n)$ , 如果蜗牛位于第 $i$ 根竹竿的高度为 $a_{i}$ 的位置 $\left(x_{i}, a_{i}\right)$ , 就可以瞬间到达第 $i + 1$ 根竹竿的高度为 $b_{i+1}$ 的位置 $\left(x_{i+1}, b_{i+1}\right)$ , 请计算蜗牛最少需要多少秒才能到巡目的地。

【输入格式】

输入共 $1 + n$ 行, 第一行为一个正整数 $n$ ;

第二行为 $n$ 个正整数 $x_{1}, x_{2}, \ldots, x_{n}$ ;

后面 $n - 1$ 行, 每行两个正整数 $a_{i}, b_{i+1}$ 。

【输出格式】

输出共一行, 一个浮点数表示答案 (四舍五入保留两位小数)。

【样例输入】

$\begin{array}{lll}3\end{array}$

$\begin{array}{lll}1 & 10 & 11\end{array}$

$\begin{array}{lll}1 & 1\end{array}$

$\begin{array}{lll}2 & 1\end{array}$

【样例输出】

$\begin{array}{lll}4.20\end{array}$

【样例说明】

蜗牛路线:

$\rightarrow(1,0) \rightarrow(1,1) \rightarrow(10,1) \rightarrow(10,0) \rightarrow(11,0)$ , 花费时间为 $1+\frac{1}{0.7}+$ $0+\frac{1}{1.3}+1 \approx 4.20$

【评测用例规模与约定】

对于 $\%$ 的数据, 保证 $\leq 15$ ;

对于 $\%$ 的数据, 保证 $\leq 10^{5}, a_{i}, b_{i} \leq 10^{4}, x_{i} \leq 10^{9}$ 。

试题 F: 合并区域

时间限制: $\mathrm{~s}$ 内存限制: 512.0MB 本题总分: 15 分

【问题描述】

小蓝在玩一款种地游戏。现在他被分配给了两块大小均为 $\times N$ 的正方形区域。这两块区域都按照 $\times N$ 的规格进行了均等划分, 划分成了若干块面积相同的小区域, 其中每块小区域要么足岩石, 要么就足土壤, 在垂直或者水平方问上相邻的土壤可以组成一块土地。现在小蓝想要对这两块区域沿着边缘进行合并, 他想知道合并以后可以得到的最大的一块土地的面积定多少 (土地的面积就足土地中土增小区域的块数)？

在进行合并时, 小区域之间必须对齐。可以在两块方形区域的任何一条边上进行合并, 可以对两块方形区域进行 90 度、 180 度、 270 度、 360 度的旋转,但不可以进行上下或左右翻转, 并月.两块方形区域不㕽以发牛重叠。

【输入格式】

第一行一个整数 $N$ 表示区域大小。

接下来 $N$ 行表示第一块区域, 每行 $N$ 个值为 0 或 1 的整数, 相邻的整数之间用空格进行分隔。值为 0 表示这块小区域是岩石, 值为 1 表示这块小区域是土壤。

再接下来 $N$ 行表示第二块区域, 每行 $N$ 个值为 0 或 1 的整数, 相邻的整数之间用空格进行分隔。值为 0 表示这块小区域是岩石, 值为 1 表示这块小区域是土壤。

【输出格式】

一个整数表示将两块区域合并之后可以产生的最大的土地面积。

【样例输入】

$\begin{array}{llll}4\end{array}$

$\begin{array}{llll}0 & 1 & 1 & 0\end{array}$

$\begin{array}{llll}1 & 0 & 1 & 1\end{array}$

$\begin{array}{llll}1 & 0 & 1 & 0\end{array}$

$\begin{array}{llll}1 & 1 & 1 & 0\end{array}$

$\begin{array}{llll}0 & 0 & 1 & 0\end{array}$

$\begin{array}{llll}0 & 1 & 1 & 0\end{array}$

$\begin{array}{llll}1 & 0 & 0 & 0\end{array}$

$\begin{array}{llll}1 & 1 & 1 & 1\end{array}$

【样例输出】

$\begin{array}{llll}15\end{array}$

【样例说明】
在这里插入图片描述

第一张图展示了样例中的两块区域的布局。第二张图展示了其中一种最佳的合并方式, 此时最大的土地面积为 15 。

【评测用例规模与约定】

对于 $\%$ 的数据， $\leq N \leq 5$ 。

对于 $\%$ 的数据, $\leq N \leq 15$ 。

对于 $\%$ 的数据, $\leq N \leq 50$ 。

试题 $\mathrm{G}:$ 买二赠一

时间限制: $\mathrm{~s}$ 内存限制: $\mathrm{MB}$ 本题总分: 20 分

【问题描述】

某商场有 $N$ 件商品, 其中第 $i$ 件的价格是 $A_{i}$ 。现在该商场正在进行 “买二赠一” 的优惠活动, 具体规则是:

每购买 2 件商品, 假设其中较便宜的价格足 $P$ (如果两件商品价格一样,则 $P$ 等于其中一件商品的价格), 就可以从剩余商品中任选一件价格不超过 $\frac{P}{2}$ 的商品, 免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商品, 但是每件商品只能被购买或免费获得一次。

小朋想知道如果要拿下所有商品 (包含购买和免费狄得), 至少要化费多少钱?

【输入格式】

第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数, 他表 $A_{1}, A_{2}, A_{3}, \ldots, A_{N}$ 。

【输出格式】

输出一个整数, 代表答案。

【样例输入】

$\begin{array}{lllllll} 7\end{array}$

$\begin{array}{lllllll}1 & 4 & 2 & 8 & 5 & 7 & 1\end{array}$

【样例输出】

$\begin{array}{lllllll}25\end{array}$

【样例说明】

小明可以先购买价格 4 和 8 的商品, 免费获得一件价格为 1 的商品; 再后买价格为 5 和 7 的商品, 免费获得价格为 2 的商品; 最后单独购买剩下的一件价格为 1 的商品。总计花费 $4 + 8 + 5 + 7 + 1 = 25$ 。不存在花费更低的方案。

【评测用例规模与约定】

对于 $\%$ 的数据, $\leq N \leq 20$ 。

对于 $\%$ 的数据, $\leq N \leq 5 \times 10^{5}, 1 \leq A_{i} \leq 10^{9}$ 。

试题 $\mathrm{H}$ : 合并石子

时间限制: $\mathrm{~s}$ 内存限制: $\mathrm{MB}$ 本题总分: 20 分

【问题描述】

在染面从左至右横向摆放着 $N$ 堆石子。每一堆石子都有着相同的商色, 颜色可能是颜色 0 , 颜色 1 或者颜色 2 中的其中一种。

现在要对石了进行合并, 规定每次只能选择位真相邻并且.颜色相同的两堆石了进行合并。合并后新堆的相对位置保持不变, 新堆的石了数目为所选择的两堆石子数日之和, 并且新堆石子的颜色也会发生循环式的变化。具休来说:两堆颜色 0 的石子合并后的石子堆为颜色 1 , 两堆颜色 1 的石子合并后的石子堆为颜色 2 , 两堆颜色 2 的石子合并后的石子堆为颜色 0 。木次合并的花费为所选择的两堆石子的数日之和。

掵出 $N$ 堆石子以及他们的初始颜色, 请问最少可以将它们合并为多少堆石子? 如果有多种營案, 选择其中合并总花费最小的一种, 合并总花费指的足在所有的合并操作山, 产牛的合并优费的总和。

【输入格式】

第一行一个正整数 $N$ 表示石了堆数。

第二行包含 $N$ 个用空格分隔的正整数, 表示从左至右每一堆石子的数目。

第二行包含 $N$ 个值为 0 或 1 或 2 的整数表示每堆石头的颜色。

【输出格式】

一行包含两个整数, 用空格分隔。其中第一个整数表示合并后数目最少的石头堆数, 第二个整数表示对应的最小优费。

【样例输入】

$\begin{array}{llllll}5\end{array}$

$\begin{array}{llllll}5& 10 & 1 & 8 & 6\end{array}$

$\begin{array}{llllll}1 & 1 & 0 & 2 & 2\end{array}$

【样例输出】

$\begin{array}{llllll}2 & 44\end{array}$

【样例说明】

在这里插入图片描述

上图亚示了两种不同的合并方式。其山节点山标朋了每一堆的石了数目,在方括号山标注了当前堆石了的颜色属性。在图的这种合并方式坟终剩下了两堆石了, 所, 生的合并总化费为 $15 + 14 + 15 = 44$ ; 右图的这种合并方式最终也剩下了两堆石了, 但, 生的合并总化费为 $14 + 15 + 25 = 54$ 。综上所述, 我们选择合并花费为 44 的这种方式作为答案。

【评测用例规模与约定】

对于 $\%$ 的评测用例, $\leq N \leq 10$ 。

对于 $\%$ 的评测用例, $\leq N \leq 50$ 。

对于 $\%$ 的评测用例, $\leq N \leq 300,1 \leq$ 每堆石子的数目 $\leq 1000$ 。

试题 I：最大开支

时间限制: $\mathrm{~s}$ 内存限制: $\mathrm{MB}$ 本题总分: 25 分

【问题描述】

小蓝所在学校周边新开业了一家游乐园, 小蓝作为班长, 打算组织大家去游乐园玩。已知一共有 $N$ 个人参加这次活动, 游乐园有 $M$ 个娱乐项目, 每个项目都需要买门票后才可进去游玩。门票的价格并不足周定的, 团则的人越多单价越便宣, 当团钊的人数大于某个阇值时, 这些团钊的人便可以免费进入项日进行游玩。这 $M$ 个娱乐项日足独立的, 所以只有选择了同一个项目的人才可以参与这个项日的团购。第 $i$ 个项目的门票价格 $H_{i}$ 与团则的人数 $X$ 的关系可以看作定一个函数:

$H_{i}(X)=\max \left(K_{i} \times X+B_{i}, 0\right)$

$\max$ 表示取二者之山的最大值。当 $H_{i}=0$ 时说朋可购人数达到了此项目的免单划值

这 $N$ 个人可以根据白已的喜好选择 $M$ 个娱乐项日中的一种, 或者有些人对这些娱乐项日都没有兴趣, 也可以选择不去任何一个项日。每个人最多只会选择一个娱乐项日, 如果多个人选择了同一个娱乐项日, 那么他们都将享受对应的团购价格。小䍀想知道他至少需要准各多少钱, 使得无论大家如何选择,他都有能力文付得起所有 $N$ 个人则买娱乐项目的门票钱。

【输入格式】

第一行两个整数 $N 、 M$ , 分別表示参加活动的人数和娱乐项目的个数。

接下来 $M$ 行, 每行两个整数, 其中第 $i$ 行为 $K_{i} 、 B_{i}$ , 表示第 $\mathrm{i}$ 个游乐地点的门票函数中的参数。

【输出格式】

一个整数, 表示小蓝至少需要准备多少钱, 使得大家无论如何选择项目,自己都支付得起。

【样例输入】

$\begin{array}{ll}4 & 2\end{array}$

$\begin{array}{ll}-4 & 10\end{array}$

$\begin{array}{ll}-2 &7\end{array}$

【样例输出】

$\begin{array}{ll}12\end{array}$

【样例说明】

样例中有 4 个人, 2 个娱乐项目, 我们用一个二元组 $(a, b)$ 表示 $a$ 个人选择了第一个娱乐项目, $b$ 个人选择了第二个娱乐项目, 那么就有 $4 - a - b$ 个人没有选择任何项日, 方案 $(a, b)$ 对应的门票花费为 $\max (-4 \times a+10,0) \times a+$ $\max (-2 \times b+7,0) \times b$ , 所有的可能如下所示:

$\mathbf{a}$	$\mathbf{b}$	花费
0	0	0
0	1	5
0	2	6
0	3	3
0	4	0
1	0	6
1	1	11
1	2	12
1	3	9
2	0	4
2	1	9
2	2	10
3	0	0
3	1	5
4	0	0

其中当 $a = 1, b = 2$ 时花费最大, 为 12 。此时 1 个人去第一个项目, 所以

第一个项目的单价为 $10 - 4 = 6$ , 在这个项目上的花费为 $\times 1=6: 2$ 个人去第二个项目, 所以第二个项目得单价为 $\times 2=3$ , 在这个项目上的花费为 $\times 3=6$ ; 还有 1 个人没去任何项目, 不用统计：总花费为 12 , 这是花费最大的一种方案, 所以答案为 12 。

【评测用例规模与约定】

对于 $\%$ 的评测用例, $\leq N, M \leq 10$ 。

对于 $\%$ 的评测用例, $\leq N, M \leq 1000$ 。

对于 $\%$ 的评测用例, $\leq N, M, B_{i} \leq 10^{5},-10^{5} \leq K_{i}<0$ 。

试题 $\mathrm{J}:$ 魔法阵

时间限制: $\mathrm{~s}$ 内存限制: $\mathrm{MB}$ 本题总分: 25 分

【问题描述】

魔法师小蓝为了营救自己的朋友小 $\mathrm{Q}$ , 来到了敌人布置的魔法阵。魔法阵可以看作是一幅具有 $N$ 个结点 $M$ 条边的无向图, 结点编号为 $\ldots, N-1$ ,图中没有重边和自环。敌人在每条边上都布置了陷吽, 每条边都有一个伤害属性 $w$ , 每当小蓝经过一条边时就会受到这条边对应的 $w$ 的伤害。小蓝从结点 0 出发, 沿着边行走, 想要到达结点 $N - 1$ 营救小 $\mathrm{Q}$ 。

小蓝有一种特殊的魔法可以使用, 假设一条路径按照顺序依次经过了以下 $L$ 条边: $e_1, e_2, \ldots, e_L$ (可以出现重复的边), 那么期间小蓝受到的总伤害就是 $P=\sum_{i=1}^L w\left(e_i\right), w\left(e_i\right)$ 表示边 $e_i$ 的伤害属性。如果 $\geq K$ , 那么小蓝就可以从这 $L$ 条边当中选出连续出现的 $K$ 条边 $e_c, e_{c+1}, \ldots, e_{c+K-1}$ 并免去在这 $K$ 条边行走期间所受到的伤害, 即使用魔法之后路径总伤害变为 $P^{\prime}=P-\sum_{i=c}^{c+K-1} w\left(e_i\right)$ 。注意必须恰好选出连续出现的 $K$ 条边, 所以当 $L < K$ 时无法使用魔法。

小蓝最多只可以使用一次上述的魔法, 请问从结点 0 出发到结点 $N - 1$ 受到的最小伤害是多少? 题目保证至少存在一条从结点 0 到 $N - 1$ 的路径。

【输入格式】

第一行输入三个整数, $N, K, M$ , 用空格分隔。
接下来 $M$ 行, 每行包含三个整数 $u, v, w$ , 表示结点 $u$ 与结点 $v$ 之间存在一条伤害属性为 $w$ 的无向边。

【输出格式】

输出一行, 包含一个整数, 表示小蓝从结点 0 到结点 $N - 1$ 受到的最小伤宫。

【样例输入 1】

$\begin{array}{lll}4 & 2 & 3\end{array}$

$\begin{array}{lll}0 & 1 & 2\end{array}$

$\begin{array}{lll}1 & 2& 1\end{array}$

$\begin{array}{lll}2 & 3 & 4\end{array}$

【样例输出 1】

$\begin{array}{lll} 2\end{array}$

【样例输入 2】

$\begin{array}{lll}2 & 5 & 1\end{array}$

$\begin{array}{lll}0 & 1 & 1\end{array}$

【样例输出 2】

$\begin{array}{lll}0 \end{array}$

【样例说明】

样例 1 , 存在路径: $\rightarrow 1 \rightarrow 2 \rightarrow 3, K=2$ , 如果在 $\rightarrow 1 \rightarrow 2$ 上梿用庵法, 那么答案就是 $0 + 0 + 4 = 4$ : 如果在 $\rightarrow 2 \rightarrow 3$ 上使用魔法, 那么答案就是 $2 + 0 + 0 = 2$ 。再也找不到比 2 还小的答案了, 所以答案就是 2 。

样例 2, 存在路徖: $\rightarrow 1 \rightarrow 0 \rightarrow 1 \rightarrow 0 \rightarrow 1, K=5$ , 这条路径总计佁好

【评测用例规模与约定】

对于 $\%$ 的评议用例， $\leq N \leq 20$ 。
对于 $\%$ 的评测用例, $\leq N \leq 100$ 。
对于 $\%$ 的评测用例， $\leq N \leq 1000,1 \leq M \leq \frac{N \times(N-1)}{2}, 1 \leq K \leq 10$ , $\leq u, v \leq N-1,1 \leq w \leq 1000$ 。