CSP-S 2026 预测模拟卷（一）。原创训练，非官方试题。

时间限制：2.0 s 内存限制：512 MiB 分值：100 分

题目描述

有 n 个城市和 m 条双向道路，道路长度为 w。小 P 从 1 到 n，有 k 张优惠券。经过一条道路可消耗一张券，使该道路代价变为 floor(w/2)。每条道路至多使用一张券，券可不用完。求最小总代价。

输入格式

第一行 n,m,k。接下来 m 行 u,v,w。

输出格式

输出最小总代价，保证 1 与 n 连通。

样例 #1

4 4 1
1 2 8
2 4 8
1 3 5
3 4 20

12

样例 #2

3 3 2
1 2 9
2 3 9
1 3 20

8

数据范围

2<=n<=210^5；1<=m<=410^5；0<=k<=10；1<=w<=10^9。

测试点配置

20 个等分测试点，每点 5 分；Subtask ID 从 0 开始，共 10 组，每组包含连续两个测试点。