Preparing NOJ

和MM逛南邮

2000ms 65536K

Description:

Openxxx生日那天,他要带着他的MM逛一逛南邮的校园。南邮校园可以看成是一个无向图,Openxxx和他的MM将从学校门口出发,走过一些道路,最终回到学校门口。Openxxx不会带着MM两次经过同一条道路,因此每条道路最多被走过一次。每条道路都有两种属性TH,分别表示走过这条道路所需的时间以及沿途的风景能够给Openxxx和他的MM带去的幸福指数。Openxxx希望逛校园的时间能够尽可能的长,但逛得太久MM会感觉疲惫,所以逛校园的时间应当不小于T1且不大于T2。同时,Openxxx希望和他的MM能够获得尽可能多的幸福指数。听说你是个很有天赋的编程能手,希望你帮助Openxxx找到一条最优的逛校园路线。

Input:

多组测试数据,每组数据第1行输入四个正整数N,M,T1,T2N表示图中的顶点个数(用0,1,……,N-1作为各个顶点的编号,其中0号顶点代表学校门口),M表示图中的边数,T1,T2分别代表逛校园时间的下限和上限。第2行到M+1行每行输入四个非负整数X,Y,T,H,表示顶点X到顶点Y有一条需要T时间通过,且幸福指数为H的道路。输入数据保证不会有重边和自环。( 3N10, NM20, 1T110000, T1T210000, 0X,Y<N0T,H10000 ) 输入直至文件结尾。

Output:

每组数据输出一行一个整数,最优路线的幸福指数MaxH;如果没有满足要求的路线,则输出 -1”(不包含双引号)。

Sample Input:

3 3 1 10000
0 1 100 100
1 2 100 100
0 2 100 100
4 4 1 10000
0 1 100 100
1 2 100 100
2 3 100 100
1 3 100 100

Sample Output:

300
-1

Note:

 

本题由旧版NOJ导入,来源:openxxx

Info

NOJ

Provider NOJ

Code NOJ1510

Tags

Submitted 2

Passed 1

AC Rate 50%

Date 04/20/2019 10:03:10

Related

Nothing Yet