👨?💻作者簡(jiǎn)介：練習(xí)時(shí)長(zhǎng)兩年半的java博主

📖個(gè)人主頁(yè)：君臨?

🎞?文章介紹：2023年第十四屆藍(lán)橋杯javaB組省賽真題

🎉所屬專欄：算法專欄

🎁 ps：點(diǎn)贊是免費(fèi)的，卻可以讓寫(xiě)博客的作者開(kāi)心好幾天😎

文章目錄

第十四屆藍(lán)橋杯大賽軟件賽省賽

試題 A: 階乘求和【填空題】

試題 B: 幸運(yùn)數(shù)字【填空題】

試題 C: 數(shù)組分割

試題 D: 矩形總面積

試題 E: 蝸牛

試題 F: 合并區(qū)域

試題 G: 買(mǎi)二贈(zèng)一

試題 H: 合并石子

試題 I: 最大開(kāi)支

試題 J: 魔法陣

---

第十四屆藍(lán)橋杯大賽軟件賽省賽（總分：150分）

試題 A: 階乘求和【填空題】

本題總分：5 分

【問(wèn)題描述】

令 S = 1! + 2! + 3! + ... + 202320232023!，求 S 的末尾 9 位數(shù)字。 提示：答案首位不為 0。

【答案提交】

這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一 個(gè)整數(shù)，在提交答案時(shí)只填寫(xiě)這個(gè)整數(shù)，填寫(xiě)多余的內(nèi)容將無(wú)法得分。

思路：

利用java的BigInteger求 S = 1! + 2! + 3! + ... + 200!的末尾 9 位數(shù)字。

試題 B: 幸運(yùn)數(shù)字【填空題】

本題總分：5 分

【問(wèn)題描述】

哈沙德數(shù)是指在某個(gè)固定的進(jìn)位制當(dāng)中，可以被各位數(shù)字之和整除的正整 數(shù)。例如 126 是十進(jìn)制下的一個(gè)哈沙德數(shù)，因?yàn)?(126)10 mod (1+2+6) = 0；126也是八進(jìn)制下的哈沙德數(shù)，因?yàn)?(126)10 = (176)8，(126)10 mod (1 + 7 + 6) = 0； 同時(shí) 126 也是 16 進(jìn)制下的哈沙德數(shù)，因?yàn)?(126)10 = (7e)16，(126)10 mod (7 + e) = 0。小藍(lán)認(rèn)為，如果一個(gè)整數(shù)在二進(jìn)制、八進(jìn)制、十進(jìn)制、十六進(jìn)制下均為哈沙德數(shù)，那么這個(gè)數(shù)字就是幸運(yùn)數(shù)字，第 1 至第 10 個(gè)幸運(yùn)數(shù)字的十進(jìn)制表示 為：1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . ?，F(xiàn)在他想知道第 2023 個(gè)幸運(yùn)數(shù)字是多少？你只需要告訴小藍(lán)這個(gè)整數(shù)的十進(jìn)制表示即可。

【答案提交】

這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個(gè)整數(shù)，在提交答案時(shí)只填寫(xiě)這個(gè)整數(shù)，填寫(xiě)多余的內(nèi)容將無(wú)法得分。

思路：

暴力枚舉

試題 C: 數(shù)組分割

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：10 分

【問(wèn)題描述】

小藍(lán)有一個(gè)長(zhǎng)度為 N 的數(shù)組 A = [A0, A1, . . . , AN?1]。現(xiàn)在小藍(lán)想要從 A 對(duì)應(yīng)的數(shù)組下標(biāo)所構(gòu)成的集合 I = {0, 1, 2, . . . , N ? 1} 中找出一個(gè)子集 R1，那么R1在I 中的補(bǔ)集為R2。記 S1 = ∑r∈R1 Ar，S2 = ∑r∈R2 Ar，我們要求 S1 和 S2 均為偶數(shù)，請(qǐng)問(wèn)在這種情況下共有多少種不同的 R1。當(dāng) R1 或 R2 為空集時(shí)我們將 S1 或 S2 視為0。

【輸入格式】

第一行一個(gè)整數(shù)T，表示有T 組數(shù)據(jù)。 接下來(lái)輸入T 組數(shù)據(jù)，每組數(shù)據(jù)包含兩行：第一行一個(gè)整數(shù) N，表示數(shù)組A 的長(zhǎng)度；第二行輸入N 個(gè)整數(shù)從左至右依次為 A0, A1, . . . , AN?1，相鄰元素之間用空格分隔。

【輸出格式】

對(duì)于每組數(shù)據(jù)，輸出一行，包含一個(gè)整數(shù)表示答案，答案可能會(huì)很大，你需要將答案對(duì) 1000000007 進(jìn)行取模后輸出。

【樣例輸入】

2
2?
6?6
2?
1 6

【樣例輸出】

4
0

【樣例說(shuō)明】

對(duì)于第一組數(shù)據(jù)，答案為 4。（注意：大括號(hào)內(nèi)的數(shù)字表示元素在數(shù)組中的下標(biāo)。）

R1 = {0}, R2 = {1}；此時(shí) S1 = A0 = 6 為偶數(shù), S2 = A1 = 6 為偶數(shù)。

R1 = {1}, R2 = {0}；此時(shí) S1 = A1 = 6 為偶數(shù), S2 = A0 = 6 為偶數(shù)。

R1 = {0, 1}, R2 = {}；此時(shí) S1 = A0 + A1 = 12 為偶數(shù), S 2 = 0 為偶數(shù)。

R1 = {}, R2 = {0, 1}；此時(shí) S1 = 0 為偶數(shù), S2 = A0 + A1 = 12 為偶數(shù)。

對(duì)于第二組數(shù)據(jù)，無(wú)論怎么選擇，都不滿足條件，所以答案為 0。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 20% 的評(píng)測(cè)用例，1 ≤ N ≤ 10。

對(duì)于 40% 的評(píng)測(cè)用例，1 ≤ N ≤ 。

對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ T ≤ 10, 1 ≤ N ≤ ?, 0 ≤ Ai ≤ 。

思路：

暴力枚舉

試題 D: 矩形總面積

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：10 分

【問(wèn)題描述】

平面上有個(gè)兩個(gè)矩形 R1 和 R2，它們各邊都與坐標(biāo)軸平行。設(shè) (x1, y1) 和(x2, y2) 依次是 R1 的左下角和右上角坐標(biāo)，(x3, y3) 和 (x4, y4) 依次是 R2 的左下角和右上角坐標(biāo)，請(qǐng)你計(jì)算 R1和R2的總面積是多少？

注意：如果 R1 和 R2 有重疊區(qū)域，重疊區(qū)域的面積只計(jì)算一次。

【輸入格式】

輸入只有一行，包含 8 個(gè)整數(shù)，依次是：x1，y1，x2，y2，x3，y3，x4 和 y4。

【輸出格式】

一個(gè)整數(shù)，代表答案。

【樣例輸入】

2 1 7 4 5 3 8 6

【樣例輸出】

22

【樣例說(shuō)明】

樣例中的兩個(gè)矩形如圖所示：

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 20% 的數(shù)據(jù)，R1 和 R2 沒(méi)有重疊區(qū)域。

對(duì)于 20% 的數(shù)據(jù)，其中一個(gè)矩形完全在另一個(gè)矩形內(nèi)部。

對(duì)于 50% 的數(shù)據(jù)，所有坐標(biāo)的取值范圍是 [0,?]。

對(duì)于 100% 的數(shù)據(jù)，所有坐標(biāo)的取值范圍是 [0,?]。

思路：

if條件判斷，暴力枚舉每一種情況

試題 E: 蝸牛

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：15 分

【問(wèn)題描述】

這天，一只蝸牛來(lái)到了二維坐標(biāo)系的原點(diǎn)。 在 x 軸上長(zhǎng)有n 根竹竿。它們平行于y 軸，底部縱坐標(biāo)為 0，橫坐標(biāo)分別為 x1, x2, ..., xn。竹竿的高度均為無(wú)限高，寬度可忽略。蝸牛想要從原點(diǎn)走到第n個(gè)竹竿的底部也就是坐標(biāo) (xn, 0)。它只能在 x 軸上或者竹竿上爬行，在x 軸 上爬行速度為1 單位每秒；由于受到引力影響，蝸牛在竹竿上向上和向下爬行的速度分別為 0.7 單位每秒和 1.3 單位每秒。 為了快速到達(dá)目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之間建立了傳送門(mén)（0 < i < n），如果蝸牛位于第 i 根竹竿的高度為 ai 的位置 (xi , ai)，就可以瞬間到達(dá)第 i + 1 根竹竿的高度為 bi+1 的位置 (xi+1, bi+1)，請(qǐng)計(jì)算蝸牛最少需要多少秒才能到達(dá)目的地。

【輸入格式】

輸入共1 + n 行，第一行為一個(gè)正整數(shù) n；

第二行為n 個(gè)正整數(shù) x1, x2, . . . , xn；

后面 n ? 1 行，每行兩個(gè)正整數(shù) ai , bi+1。

【輸出格式】

輸出共一行，一個(gè)浮點(diǎn)數(shù)表示答案（四舍五入保留兩位小數(shù)）。

【樣例輸入】?

3
1 10 11
1 1
2 1

【樣例輸出】

4.20

【樣例說(shuō)明】

蝸牛路線：(0, 0) → (1, 0) → (1, 1) → (10, 1) → (10, 0) → (11, 0)，花費(fèi)時(shí)間為 1 + 1/0.7 + 0 + 1/1.3 + 1 ≈ 4.20

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 20% 的數(shù)據(jù),保證 n ≤15.

對(duì)于 100% 的數(shù)據(jù)，保證 n ≤ ，ai , bi ≤ ，xi ≤ 。

思路：

動(dòng)態(tài)規(guī)劃

試題 F: 合并區(qū)域

時(shí)間限制: 2.0s 內(nèi)存限制: 512.0MB 本題總分：15 分

【問(wèn)題描述】

小藍(lán)在玩一款種地游戲?，F(xiàn)在他被分配給了兩塊大小均為 N × N 的正方形區(qū)域。這兩塊區(qū)域都按照 N × N 的規(guī)格進(jìn)行了均等劃分，劃分成了若干塊面積相同的小區(qū)域，其中每塊小區(qū)域要么是巖石，要么就是土壤，在垂直或者水平方向上相鄰的土壤可以組成一塊土地。現(xiàn)在小藍(lán)想要對(duì)這兩塊區(qū)域沿著邊緣進(jìn)行合并，他想知道合并以后可以得到的最大的一塊土地的面積是多少（土地的面積就是土地中土壤小區(qū)域的塊數(shù)）？在進(jìn)行合并時(shí)，小區(qū)域之間必須對(duì)齊?？梢栽趦蓧K方形區(qū)域的任何一條邊上進(jìn)行合并，可以對(duì)兩塊方形區(qū)域進(jìn)行 90 度、180 度、270 度、360 度的旋轉(zhuǎn)， 但不可以進(jìn)行上下或左右翻轉(zhuǎn)，并且兩塊方形區(qū)域不可以發(fā)生重疊。

【輸入格式】

第一行一個(gè)整數(shù) N 表示區(qū)域大小。 接下來(lái) N 行表示第一塊區(qū)域，每行 N 個(gè)值為 0 或 1 的整數(shù)，相鄰的整數(shù) 之間用空格進(jìn)行分隔。值為 0 表示這塊小區(qū)域是巖石，值為 1 表示這塊小區(qū)域 是土壤。 再接下來(lái) N 行表示第二塊區(qū)域，每行 N 個(gè)值為 0 或 1 的整數(shù)，相鄰的整 數(shù)之間用空格進(jìn)行分隔。值為 0 表示這塊小區(qū)域是巖石，值為 1 表示這塊小區(qū)域是土壤。

【輸出格式】

一個(gè)整數(shù)表示將兩塊區(qū)域合并之后可以產(chǎn)生的最大的土地面積。

?【樣例輸入】

4
0 1 1 0
1 0 1 1
1 0 1 0
1 1 1 0
0 0 1 0
0 1 1 0
1 0 0 0
1 1 1 1

【樣例輸出】

15

【樣例說(shuō)明】

?第一張圖展示了樣例中的兩塊區(qū)域的布局。第二張圖展示了其中一種最佳 的合并方式，此時(shí)最大的土地面積為 15。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的數(shù)據(jù)，1 ≤ N ≤ 5。

對(duì)于 60% 的數(shù)據(jù)，1 ≤ N ≤ 15。

對(duì)于 100% 的數(shù)據(jù)，1 ≤ N ≤ 50。

思路：

DFS

下圖的兩種情況是坑，所以還是老老實(shí)實(shí)用dfs枚舉每一種情況吧。

試題 G: 買(mǎi)二贈(zèng)一

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：20 分

【問(wèn)題描述】

某商場(chǎng)有 N 件商品，其中第 i 件的價(jià)格是 Ai?，F(xiàn)在該商場(chǎng)正在進(jìn)行 “買(mǎi)二 贈(zèng)一” 的優(yōu)惠活動(dòng)，具體規(guī)則是： 每購(gòu)買(mǎi) 2 件商品，假設(shè)其中較便宜的價(jià)格是 P（如果兩件商品價(jià)格一樣， 則 P 等于其中一件商品的價(jià)格），就可以從剩余商品中任選一件價(jià)格不超過(guò) P/2 的商品，免費(fèi)獲得這一件商品?？梢酝ㄟ^(guò)反復(fù)購(gòu)買(mǎi) 2 件商品來(lái)獲得多件免費(fèi)商品，但是每件商品只能被購(gòu)買(mǎi)或免費(fèi)獲得一次。 小明想知道如果要拿下所有商品（包含購(gòu)買(mǎi)和免費(fèi)獲得），至少要花費(fèi)多少錢(qián)？

【輸入格式】

第一行包含一個(gè)整數(shù) N。

第二行包含 N 個(gè)整數(shù)，代表 A1, A2, A3, . . . ，AN。

【輸出格式】

輸出一個(gè)整數(shù)，代表答案。

【樣例輸入】

7

1 4 2 8 5 7 1

【樣例輸出】

25

【樣例說(shuō)明】

小明可以先購(gòu)買(mǎi)價(jià)格 4 和 8 的商品，免費(fèi)獲得一件價(jià)格為1 的商品；再后買(mǎi)價(jià)格為 5 和 7 的商品，免費(fèi)獲得價(jià)格為 2 的商品；最后單獨(dú)購(gòu)買(mǎi)剩下的一件價(jià)格為 1 的商品?？傆?jì)花費(fèi) 4 + 8 + 5 + 7 + 1 = 25。不存在花費(fèi)更低的方案。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的數(shù)據(jù)，1 ≤ N ≤ 20。

對(duì)于 100% 的數(shù)據(jù)，1 ≤ N ≤ 5 × ，1 ≤ Ai ≤ 。

試題 H: 合并石子

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：20 分

【問(wèn)題描述】

在桌面從左至右橫向擺放著 N 堆石子。每一堆石子都有著相同的顏色，顏色可能是顏色 0，顏色 1 或者顏色 2 中的其中一種。 現(xiàn)在要對(duì)石子進(jìn)行合并，規(guī)定每次只能選擇位置相鄰并且顏色相同的兩堆石子進(jìn)行合并。合并后新堆的相對(duì)位置保持不變，新堆的石子數(shù)目為所選擇的兩堆石子數(shù)目之和，并且新堆石子的顏色也會(huì)發(fā)生循環(huán)式的變化。具體來(lái)說(shuō)： 兩堆顏色 0 的石子合并后的石子堆為顏色 1，兩堆顏色 1 的石子合并后的石子堆為顏色 2，兩堆顏色 2 的石子合并后的石子堆為顏色 0。本次合并的花費(fèi)為所選擇的兩堆石子的數(shù)目之和。 給出 N 堆石子以及他們的初始顏色，請(qǐng)問(wèn)最少可以將它們合并為多少堆石子？如果有多種答案，選擇其中合并總花費(fèi)最小的一種，合并總花費(fèi)指的是在 所有的合并操作中產(chǎn)生的合并花費(fèi)的總和。

【輸入格式】

第一行一個(gè)正整數(shù) N 表示石子堆數(shù)。 第二行包含 N 個(gè)用空格分隔的正整數(shù)，表示從左至右每一堆石子的數(shù)目。 第三行包含 N 個(gè)值為 0 或 1 或 2 的整數(shù)表示每堆石頭的顏色。

【輸出格式】

一行包含兩個(gè)整數(shù)，用空格分隔。其中第一個(gè)整數(shù)表示合并后數(shù)目最少的石頭堆數(shù)，第二個(gè)整數(shù)表示對(duì)應(yīng)的最小花費(fèi)。

【樣例輸入】

5

5 10 1 8 6

1 1 0 2 2

【樣例輸出】

2 44

【樣例說(shuō)明】

上圖顯示了兩種不同的合并方式。其中節(jié)點(diǎn)中標(biāo)明了每一堆的石子數(shù)目， 在方括號(hào)中標(biāo)注了當(dāng)前堆石子的顏色屬性。左圖的這種合并方式最終剩下了兩 堆石子，所產(chǎn)生的合并總花費(fèi)為 15 + 14 + 15 = 44；右圖的這種合并方式最終 也剩下了兩堆石子，但產(chǎn)生的合并總花費(fèi)為 14 + 15 + 25 = 54。綜上所述，我們選擇合并花費(fèi)為 44 的這種方式作為答案。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的評(píng)測(cè)用例，1 ≤ N ≤ 10。

對(duì)于 50% 的評(píng)測(cè)用例，1 ≤ N ≤ 50。

對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ N ≤ 300, 1 ≤ 每堆石子的數(shù)目 ≤ 1000。

試題 I: 最大開(kāi)支

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：25 分

【問(wèn)題描述】

小藍(lán)所在學(xué)校周邊新開(kāi)業(yè)了一家游樂(lè)園，小藍(lán)作為班長(zhǎng)，打算組織大家去游樂(lè)園玩。已知一共有 N 個(gè)人參加這次活動(dòng)，游樂(lè)園有 M 個(gè)娛樂(lè)項(xiàng)目，每個(gè)項(xiàng)目都需要買(mǎi)門(mén)票后才可進(jìn)去游玩。門(mén)票的價(jià)格并不是固定的，團(tuán)購(gòu)的人越多單價(jià)越便宜，當(dāng)團(tuán)購(gòu)的人數(shù)大于某個(gè)閾值時(shí)，這些團(tuán)購(gòu)的人便可以免費(fèi)進(jìn)入項(xiàng) 目進(jìn)行游玩。這 M 個(gè)娛樂(lè)項(xiàng)目是獨(dú)立的，所以只有選擇了同一個(gè)項(xiàng)目的人才可 以參與這個(gè)項(xiàng)目的團(tuán)購(gòu)。第 i 個(gè)項(xiàng)目的門(mén)票價(jià)格 Hi 與團(tuán)購(gòu)的人數(shù) X 的關(guān)系可以看作是一個(gè)函數(shù)：

Hi(X) = max(Ki × X + Bi , 0)

max 表示取二者之中的最大值。當(dāng) Hi = 0 時(shí)說(shuō)明團(tuán)購(gòu)人數(shù)達(dá)到了此項(xiàng)目的 免單閾值。 這 N 個(gè)人可以根據(jù)自己的喜好選擇 M 個(gè)娛樂(lè)項(xiàng)目中的一種，或者有些人 對(duì)這些娛樂(lè)項(xiàng)目都沒(méi)有興趣，也可以選擇不去任何一個(gè)項(xiàng)目。每個(gè)人最多只會(huì)選擇一個(gè)娛樂(lè)項(xiàng)目，如果多個(gè)人選擇了同一個(gè)娛樂(lè)項(xiàng)目，那么他們都將享受對(duì)應(yīng)的團(tuán)購(gòu)價(jià)格。小藍(lán)想知道他至少需要準(zhǔn)備多少錢(qián)，使得無(wú)論大家如何選擇， 他都有能力支付得起所有 N 個(gè)人購(gòu)買(mǎi)娛樂(lè)項(xiàng)目的門(mén)票錢(qián)。

【輸入格式】

第一行兩個(gè)整數(shù) N、M，分別表示參加活動(dòng)的人數(shù)和娛樂(lè)項(xiàng)目的個(gè)數(shù)。 接下來(lái) M 行，每行兩個(gè)整數(shù)，其中第 i 行為 Ki、Bi，表示第 i 個(gè)游樂(lè)地點(diǎn) 的門(mén)票函數(shù)中的參數(shù)。

【輸出格式】

一個(gè)整數(shù)，表示小藍(lán)至少需要準(zhǔn)備多少錢(qián)，使得大家無(wú)論如何選擇項(xiàng)目， 自己都支付得起。

【樣例輸入】

4 2

-4 10

-2 7

【樣例輸出】

12

【樣例說(shuō)明】

樣例中有 4 個(gè)人，2 個(gè)娛樂(lè)項(xiàng)目，我們用一個(gè)二元組 (a, b) 表示 a 個(gè)人選擇了第一個(gè)娛樂(lè)項(xiàng)目，b 個(gè)人選擇了第二個(gè)娛樂(lè)項(xiàng)目，那么就有 4 ? a ? b 個(gè) 人沒(méi)有選擇任何項(xiàng)目，方案 (a, b) 對(duì)應(yīng)的門(mén)票花費(fèi)為 max(?4 × a + 10, 0) × a + max(?2 × b + 7, 0) × b，所有的可能如下所示：

思路：

貪心算法。

計(jì)算每個(gè)項(xiàng)目多一個(gè)人參加時(shí)造成的費(fèi)用變化量，貪心的參加費(fèi)用變化最多的項(xiàng)目。

試題 J: 魔法陣

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：25 分

【問(wèn)題描述】

魔法師小藍(lán)為了營(yíng)救自己的朋友小Q，來(lái)到了敵人布置的魔法陣。魔法陣可以看作是一幅具有 N 個(gè)結(jié)點(diǎn) M 條邊的無(wú)向圖，結(jié)點(diǎn)編號(hào)為 0, 1, 2, . . . , N ? 1， 圖中沒(méi)有重邊和自環(huán)。敵人在每條邊上都布置了陷阱，每條邊都有一個(gè)傷害屬性 w，每當(dāng)小藍(lán)經(jīng)過(guò)一條邊時(shí)就會(huì)受到這條邊對(duì)應(yīng)的 w 的傷害。小藍(lán)從結(jié)點(diǎn) 0出發(fā)，沿著邊行走，想要到達(dá)結(jié)點(diǎn) N ? 1 營(yíng)救小 Q。 小藍(lán)有一種特殊的魔法可以使用，假設(shè)一條路徑按照順序依次經(jīng)過(guò)了以下L 條邊：e1, e2, . . . , eL（可以出現(xiàn)重復(fù)的邊），那么期間小藍(lán)受到的總傷害就是P = ∑L i=1 w(ei)，w(ei) 表示邊 ei 的傷害屬性。如果 L ≥ K，那么小藍(lán)就可以從 這 L 條邊當(dāng)中選出連續(xù)出現(xiàn)的 K 條邊 ec , ec+1, . . . , ec+K?1 并免去在這 K 條邊行走期間所受到的傷害，即使用魔法之后路徑總傷害變?yōu)?P ′ = P ? ∑c+K?1 i = c w(ei)。 注意必須恰好選出連續(xù)出現(xiàn)的 K 條邊，所以當(dāng) L < K 時(shí)無(wú)法使用魔法。 小藍(lán)最多只可以使用一次上述的魔法，請(qǐng)問(wèn)從結(jié)點(diǎn) 0 出發(fā)到結(jié)點(diǎn) N ? 1 受 到的最小傷害是多少？題目保證至少存在一條從結(jié)點(diǎn) 0 到 N ? 1 的路徑。

【輸入格式】

第一行輸入三個(gè)整數(shù)，N, K, M，用空格分隔。 接下來(lái) M 行，每行包含三個(gè)整數(shù) u, v,w，表示結(jié)點(diǎn) u 與結(jié)點(diǎn) v 之間存在一 條傷害屬性為 w 的無(wú)向邊。

【輸出格式】

輸出一行，包含一個(gè)整數(shù)，表示小藍(lán)從結(jié)點(diǎn) 0 到結(jié)點(diǎn) N ? 1 受到的最小傷害。

【樣例輸入 1】

4 2 3

0 1 2

1 2 1

2 3 4

【樣例輸出 1】

2

【樣例輸入 2】

2 5 1

0 1 1

【樣例輸出 2】

0

【樣例說(shuō)明】

樣例 1，存在路徑：0 → 1 → 2 → 3，K = 2，如果在 0 → 1 → 2 上使用魔 法，那么答案就是 0 + 0 + 4 = 4；如果在 1 → 2 → 3 上使用魔法，那么答案就 是 2 + 0 + 0 = 2。再也找不到比 2 還小的答案了，所以答案就是 2。 樣例 2，存在路徑：0 → 1 → 0 → 1 → 0 → 1，K = 5，這條路徑總計(jì)恰好 走了 5 條邊，所以正好可以用魔法消除所有傷害，答案是 0。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的評(píng)測(cè)用例，1 ≤ N ≤ 20。

對(duì)于 50% 的評(píng)測(cè)用例，1 ≤ N ≤ 100。

對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ N ≤ 1000, 1 ≤ M ≤ N×(N?1)/2 ，1 ≤ K ≤ 10, 0 ≤ u, v ≤ N ? 1，1 ≤ w ≤ 1000。

?總結(jié)：

在考場(chǎng)上，一張卷子做下來(lái)，發(fā)現(xiàn)自己只會(huì)枚舉這一種算法了😅，來(lái)自算法小白的藍(lán)橋杯總結(jié)。用java代碼實(shí)現(xiàn)解題，以后補(bǔ)上。

?

結(jié)束語(yǔ)

• 記錄生活，分享知識(shí)！
• 本人還在不斷學(xué)習(xí)中，如有問(wèn)題可留言交流學(xué)習(xí)！