奢侈的旅行

提交数: 39, 通过率: 69.23%, 平均分: 70.26

题目描述:

高玩小 Q 不仅喜欢玩寻宝游戏,还喜欢一款升级养成类游戏。在这个游戏的世界地图中一共有 \(n\) 个城镇,编号依次为 \(1\) 到 \(n\)。

这些城镇之间有 \(m\) 条单向道路,第 \(i\) 条单项道路包含四个参数 \(u_i, v_i, a_i, b_i\),表示一条从 \(u_i\) 号城镇出发,在 \(v_i\) 号城镇结束的单向道路,因为是单向道路,这不意味着小 \(Q\) 可以从 \(v_i\) 沿着该道路走到 \(u_i\)。

小Q的初始等级 \(level\) 为 \(1\),每当试图经过一条道路时,需要支付\(cost=\log_2\frac{level + a_i}{level}\) 点积分,并且经过该道路后,小 Q 的等级会提升 \(a_i\) 级,到达 \(level+a_i\) 级。但是每条道路都会在一定意义上歧视低消费玩家,准确地说,如果该次所需积分 \(cost<b_i\),那么小 Q 不能经过该次道路,也不能提升相应的等级。

注意:本游戏中等级为正整数,但是积分可以是任意实数。

小 Q 位于 \(1\) 号城镇,等级为 \(1\),现在为了做任务要到 \(n\) 号城镇去。这将会是一次奢侈的旅行,请写一个程序帮助小 Q 找到需要支付的总积分最少的一条路线,或判断这是不可能的。

输入格式:

第一行包含一个正整数 \(T (1\leq T\leq 30)\),表示测试数据的组数。

每组数据第一行包含两个整数 \(n, m (2\leq n\leq 50000, 1\leq m\leq 100000)\),表示城镇数和道路数。

接下来 \(m\) 行,每行四个整数 \(u_i, v_i, a_i, b_i (1\leq u_i,v_i\leq n, u_i\neq v_i, 0\leq a_i\leq 10^9, 0\leq b_i\leq 60)\),分别表示每条单向道路。

输出格式:

对于每组数据,输出一行一个整数,即最少所需的总积分的整数部分,如:\(4.9999\) 输出 \(4\),\(1.0\) 输出 \(1\)。若不存在合法路线请输出 \(−1\)。

样例输入:

1
3 3
1 2 3 2
2 3 1 6
1 3 5 0

样例输出:

2

提示:

请使用复杂度正确的算法。
请注意浮点数误差。

时间限制: 4000ms
空间限制: 256MB

来源: hdu 6290