← 返回题单
题单练习 最短路
← 上一题 下一题 →

A6183 | Revamping Trails G

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

农夫约翰每天都会认真检查他的奶牛。他会穿越一些编号为 $1$ 到 $M$ 的小径（$1 \leq M \leq 50,000$），从牧场 $1$ 一直走到牧场 $N$（对于测试数据给出的路径图，这段旅程总是可能的）。农夫约翰的农场上有 $N$ 个牧场（$1 \leq N \leq 10,000$），它们通过双向泥土小径连接在一起。每条小径 $i$ 连接牧场 $P1_i$ 和 $P2_i$（$1 \leq P1_i \leq N,1 \leq P2_i \leq N$），需要 $T_i$（$1 \leq T_i \leq 1,000,000$）单位时间来穿越。

他想要改造农场上的一些小径，以节省长途旅行的时间。具体来说，他将选择 $K$（$1 \leq K \leq 20$）条小径将其改造成高速公路，这将有效地将小径的穿越时间减少到 $0$。帮助 FJ 决定改造哪些小径以最小化从牧场 $1$ 到 $N$ 的最终时间。

输入格式

  • 第 $1$ 行：三个用空格分隔的整数：$N,M$ 和 $K$。
  • 第 $2$ 行到第 $M+1$ 行：第 $i+1$ 行描述小径 $i$，包含三个用空格分隔的整数：$P1_i$、$P2_i$ 和 $T_i$。

输出格式

共 $1$ 行：改造不超过 $K$ 条边后的最短路径长度。

输入输出样例

输入 #1
4 4 1 
1 2 10 
2 4 10 
1 3 1 
3 4 100
输出 #1
1
C++ 编辑器
输入
输出