3178 问题 H: 蓝桥杯2023年第十四届省赛真题-魔法阵

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

小蓝有一种特殊的魔法可以使用，假设一条路径按照顺序依次经过了以下L 条边：e₁, e₂, . . . , e_L（可以出现重复的边），那么期间小蓝受到的总伤害就是P = ∑^L_i=1 w(e_i)，w(e_i) 表示边 e_i 的伤害属性。如果L≥K，那么小蓝就可以从这 L条边当中选出连续出现的K条边 e_c , e_c+1, . . . , e_c+K−1并免去在这K 条边行走期间所受到的伤害，即使用魔法之后路径总伤害变为 P ′ = P −∑^c+K−1_i=cw(e_i)。

注意必须恰好选出连续出现的 K 条边，所以当 L < K 时无法使用魔法。

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

第一行输入三个整数，N, K, M，用空格分隔。

接下来 M 行，每行包含三个整数 u, v,w，表示结点 u 与结点 v 之间存在一条伤害属性为 w 的无向边。

输出一行，包含一个整数，表示小蓝从结点 0 到结点 N − 1 受到的最小伤害。

样例 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，这条路径总计恰好走了 5 条边，所以正好可以用魔法消除所有伤害，答案是 0。

对于 30% 的评测用例，1 ≤ N ≤ 20。

对于 50% 的评测用例，1 ≤ N ≤ 100。

对于 100% 的评测用例，1 ≤ N ≤ 1000, 1 ≤ M ≤ N×(N−1)/2，1 ≤ K ≤ 10，0 ≤ u, v ≤ N − 1，1 ≤ w ≤ 1000