#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号楼一定存在路径