#1308. 「NOI2019」回家路线

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: wjyyy

题目描述

猫国的铁路系统中有 n 个站点,从 1\sim n 编号。小猫准备从 1 号站点出发,乘坐列车回到猫窝所在的 n 号站点。它查询了能够乘坐的列车,这些列车共 m 班,从 1\sim m 编号。小猫将在 0 时刻到达 1 号站点。对于 i 号列车,它将在时刻 p_i 从站点 x_i 出发,在时刻 q_i 直达站点 y_i ,小猫只能在时刻 p_i i 号列车,也只能在时刻 q_i i 号列车。

小猫可以通过多次换乘到达 n 号站点。一次换乘是指对于两班列车,假设分别为 u 号与 v 号列车,若 y_u=x_v 并且 q_u\le p_v ,那么小猫可以乘坐完 u 号列车后在 y_u 号站点等待 p_v−q_u 个时刻,并在时刻 p_v 乘坐 v 号列车。

小猫只想回到猫窝并且减少途中的麻烦,对此它用烦躁值来衡量。

  • 小猫在站点等待时将增加烦躁值,对于一次 t(t\ge 0) 个时刻的等待,烦躁值将增加 At^2+Bt+C ,其中 A,B,C 是给定的常数。注意:小猫登上第一班列车前,即从 0 时刻起停留在 1 号站点的那些时刻也算作一次等待。
  • 若小猫最终在时刻 z 到达 n 号站点,则烦躁值将再增加 z

形式化地说,若小猫共乘坐了 k 班列车,依次乘坐的列车编号可用序列 s_1,s_2,\cdots,s_k 表示。该方案被称作一条可行的回家路线,当且仅当它满足下列两个条件:

  1. x_{s_1}=1,y_{s_k}=n
  2. 对于所有 j(1\le j<k) ,满足 y_{s_j}=x_{s_{j+1}} q_{s_j}\le p_{s_{j+1}}

对于该回家路线,小猫得到的烦躁值将为:

q_{s_k}+(A\cdot p_{s_1}^2+B\cdot p_{s_1}+C)+\sum_{j=1}^{k−1}(A(p_{s_{j+1}}−q_{s_j})^2+B(p_{s_{j+1}}−q_{s_j})+C)

小猫想让自己的烦躁值尽量小,请你帮它求出所有可行的回家路线中,能得到的最小的烦躁值。题目保证至少存在一条可行的回家路线。

输入格式

从标准输入中读入数据。

第一行五个整数 n,m,A,B,C ,变量意义见题目描述。

接下来 m 行,第 i 行四个整数 x_i,y_i,p_i,q_i ,分别表示 i 号列车的出发站、到达站、出发时刻与到达时刻。

输出格式

输出到标准输出中。

输出仅一行一个整数,表示所求的答案。

样例

样例 1 输入

3 4 1 5 10
1 2 3 4
1 2 5 7
1 2 6 8
2 3 9 10

样例 1 输出

94

样例 1 解释

共有三条可行的回家路线:

  1. 依次乘坐 1 4 号列车,得到的烦躁值为:

    10+(1\times 32+5\times 3+10)+(1\times (9-4)^2+5\times (9−4)+10)=104

  2. 依次乘坐 2 4 号列车,得到的烦躁值为:

    10+(1\times 52+5\times 5+10)+(1\times (9−7)^2+5\times (9−7)+10)=94

  3. 依次乘坐 3 4 号列车,得到的烦躁值为:

    10+(1\times 62+5\times 6+10)+(1\times (9−8)^2+5\times (9−8)+10)=102

第二条路线得到的烦躁值最小为 94

样例 2 输入

4 3 1 2 3
1 2 2 3
2 3 5 7
3 4 7 9

样例 2 输出

34

样例 3

见附加文件中的 route/route3.inroute/route3.ans

该样例的数据类型与最终测试点 5\sim 8 一致。

样例 4

见选手目录下的 route/route4.inroute/route4.ans

该样例的数据类型与最终测试点 11\sim 14 一致。

样例 5

见选手目录下的 route/route5.inroute/route5.ans

该样例的数据类型与最终测试点 18\sim 20 一致。

数据范围与提示

2\le n\le 10^5,\ 1\le m\le 2\times 10^5

0\le A\le 10,\ 0\le B,C\le 10^6

1\le x^i,y_i\le n,\ x_i\ne y_i,\ 0\le p_i<q_i\le 10^3

每个测试点的具体限制见下表:

测试点编号 n m A,B,C 特殊限制 其他特殊条件
1\sim 2 \le 100 =n-1 y_i=x_i+1
3\sim 4 \le 100 A=B=C=0
5\sim 8 \le 2000 \le 4000 x_i<y_i
9 A=B=0
10 A=0
11\sim 14
15 \le 10^5 \le 2\times 10^5 A=B=0
16\sim 17 A=0
18\sim 20