#Psp18. 4.删边问题
4.删边问题
4.删边问题
题目描述
给出一张n个点,m条边的有向图,每条边有长度和价值,要删掉一些边使得起点1到终点n的最短路不低于给定的,要在保证这个前提下使得删掉的边中的最大的价值最小,求这个最小值。
输入格式
第一行包含三个整数:n,m,T。接下来m行。
每行描述一条有向道路。
每行4个整数,u,v,len,val,分别表示这条道路的起点,终点,长度,这条道路的价值。
输出格式
如果不需要删边,输出一行两个数:-1和最短路径长度(当然,这个值大于等于T),以空格隔开。否则输出一行包含一个数:最小的价值。
数据范围
(原站未提供,导入后需人工补齐)
样例
5 5 15
1 2 6 35
2 4 8 40
1 3 6 45
3 4 3 25
4 5 5 50
25
3 2 10
1 2 5 30
2 3 6 50
-1 11
提示
对于20%的数据,n,m<=10.
对于60%的数据,n,m<=100.
对于100%的数据,n<=20000,m<=100000.
数据保证在不拆除任何道路的情况下,从1号楼到n号楼一定存在路径