题目描述
每天,FJ 需要经过一些道路去检查牛棚 n 里面的牛。农场上有 m 条双向泥土道路,编号为 1∼m。道路 i 连接牛棚 p1i 和 p2i。FJ 需要 ti 时间单位用道路 i 从 p1i 走到 p2i 或者从 p2i 走到 p1i。
他想更新一些路经来减少每天花在路上的时间。具体地说,他想更新 k 条路经,将它们所须时间减为 0。帮助 FJ 选择哪些路经需要更新使得从 1 到 n 的时间尽量少。
输入格式
第一行:三个空格分开的数:n,m,k。
第 2∼m+1 行:第 i+1 行有三个空格分开的数:p1i,p2i,ti。
输出格式
- 第一行: 更新最多 k 条路经后的最短路经长度。
4 4 1
1 2 10
2 4 10
1 3 1
3 4 100
1
数据规模与约定
对于 100% 的数据,1≤m≤50000,1≤p1i≤n,1≤p2i≤n,1≤ti≤1×106,1≤k≤20。
提示
样例中 k 是 1,更新道路 3−>4 使得从 3 到 4 的时间由 100 减少到 0。 最新最短路经是 1−>3−>4,总用时为 1 单位。
题目来源
Usaco2009 Feb Gold
补充数据约定
1≤N≤10000,1≤M≤50000,1≤K≤20,1≤Ti≤106。保证从牧场 1 能到达牧场 N。