#524. 「多校联考 Round 3」卡车

内存限制:512 MiB 时间限制:1000 ms 输入文件:truck.in 输出文件:truck.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 Y 是一个喜欢玩游戏的 OIer,在她玩过的游戏当中,最刺激的当属《欧洲卡车模拟》了。在这款游戏中,小 Y 的任务是驾驶自己的货车,在欧洲平原上,根据每条订单的要求,从起点运送货物到达终点。由于欧洲的各个国家的发展情况不同,道路的崎岖状况也有所不同。

像很多游戏一样,《欧洲卡车模拟》具有简单的养成系统,人物驾驶卡车的熟练度会随时间的流逝而上升,具体表现为能够在更少的时间内通过一条道路。

方便起见,我们作出如下的约定:

  • 欧洲可以抽象为一张 n 个点, m 条边的无向图,通过每条道路所需的时间为 w_i

  • 每条道路都具有一个崎岖度 c_i c_i 的大小将会改变通过改条道路的时间。具体地,若小 Y 在第 t 秒经过第 i 条道路,则崎岖度带来的额外时间花费为 \lfloor \frac{c_i}{t + 1} \rfloor

《欧洲卡车模拟》虽然已经是九年前的游戏了,游戏内的风景却依旧惊艳。为了欣赏异国他乡的风景,小 Y 在运输的路途中可以在某个城市停留若干时间观光。

小 Y 现在新创建了一个人物开始游戏,假设她要从 1 号点运送货物到 n 号点,请你帮她求出所需要的最少时间。

输入格式

第一行两个正整数 n, m ,表示点的个数和边的个数。

接下来 m 行,每行四个整数 u_i, v_i, w_i, c_i ,分别表示道路连接的两个城市的编号,通过该道路的时间和道路的崎岖度。

输出格式

输出一行一个整数,表示从 1 行驶到 n 所需要的最短时间,若无法到达输出 -1

样例

样例输入 1

2 1
1 2 2 3

样例输出 1

4

小 Y 在城市 1 停留 1 个单位时间,然后通过唯一的一条边,需要的时间为 2 + \lfloor \frac{3}{1 + 1} \rfloor = 3 ,总时间为 1 + 3 = 4

样例输入 2

2 3
1 2 2 3
1 2 2 1
1 1 1 1

样例输出 2

3

图中可能存在重边和自环。

样例输入 3

4 2
1 2 3 4
3 4 5 6

样例输出 3

-1

样例输入 4

6 9
1 1 0 0
1 3 1 2
1 5 2 3
5 2 16 5
2 6 1 10
3 4 3 4
3 5 3 10
5 6 1 100
4 2 0 110

样例输出 4

20

数据范围与提示

对于 100 \% 的数据, 2 \le n \le 10^5, 0 \le m \le 10^5, 1 \le u_i, v_i \le n, 0 \le w_i, c_i \le 10^9

每个测试点的详细规模见下表:

测试点编号 n \le m \le 特殊性质
1 \sim 8 5 20
9 \sim 12 10^5 图的形态是一棵树
13 \sim 16 c_i = 0
17 \sim 20 2000
21 \sim 25 10^5