#P1529. 道路翻新(revamp)

道路翻新(revamp)

【问题描述】

陈实的父亲陈老实每天都要检查一下鸡窝里的鸡。他需要从编号为1鸡窝出发,通过最近的道路走到编号为N的鸡窝。现假设农场上一共有N个鸡窝,为方便起见,用1到N的数字来编号,它们由M (1 ≤ M ≤ 50000)条双向道路连接,保证1号鸡窝一定会与N号鸡窝相连。每条道路连接的鸡窝用P1i和P2i (1 ≤ P1i, P2i≤ N)表示,通行消耗的时间用Ti (1 ≤ Ti≤ 1000000)来表示。

现在陈老实想翻新一些道路来减少每天花在路上的时间。但他最多只能翻新 (1 ≤ K ≤ 20)条道路,翻新后的道路的通行时间将变成0。请帮助陈老实选择最优的翻新方案使得从1号鸡窝到N号鸡窝的时间最短。

【输入文件】revamp.in

输入文件共M+1行; 第一行:包括三个数:N,M和K,彼此用空格分开。

第二行到M+1行:在第i+1行将会告诉你第i条道路的信息:P1i,P2i和Ti,彼此用空格分开。 N<=10000

【输出文件】revamp.out

输出文件仅一行:不超过K条道路被翻新后的最短路径长度。

【输入输出样例】

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

【样例说明】

选择翻新3→4,时间从100减到0,最短路径为1→3→4,因而总用时为1