P0690

[Usaco2009 Feb]Revamping Trails 道路升级

[Usaco2009 Feb]Revamping Trails 道路升级

每天，农夫约翰需要经过一些道路，去检查牛棚 NN 中的奶牛。农场上有 MM 条双向泥土道路，编号为 11 至 MM。道路 ii 连接牛棚 P1iP1_i 和 P2iP2_i，约翰沿道路 ii 在两个端点之间通行需要 TiT_i 个时间单位。

约翰想升级一些道路，将这些道路的通行时间降为 00，从而减少每天花在路上的时间。具体来说，他最多可以升级 KK 条道路。请帮助约翰选择需要升级的道路，使得从牛棚 11 到牛棚 NN 的最短通行时间尽可能小。

输入格式

第一行包含三个空格分隔的整数 NN、MM 和 KK。

接下来 MM 行，每行包含三个空格分隔的整数 P1iP1_i、P2iP2_i 和 TiT_i，表示第 ii 条道路连接牛棚 P1iP1_i 和 P2iP2_i，通行时间为 TiT_i。

输出格式

输出一行一个整数，表示升级最多 KK 条道路后，从牛棚 11 到牛棚 NN 的最短通行时间。

样例输入

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

样例输出

1

样例解释

升级道路 33，使得从牛棚 33 到牛棚 44 的通行时间由 100100 降为 00。此时最短路径为 1→3→41\to3\to4，总通行时间为 11。

数据范围

  • 1≤M≤5×1041\le M\le 5\times 10^4；
  • 1≤P1i≤N1\le P1_i\le N；
  • 1≤P2i≤N1\le P2_i\le N；
  • 1≤Ti≤1061\le T_i\le 10^6；
  • 1≤K≤201\le K\le 20；
  • N≤10000N\le 10000。

来源与许可

本题为 USACO 2009 年 22 月赛题目「Revamping Trails」，题面与测试数据整理自 BZOJ 1579。

样例 1

输入

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

输出

1