回家路线问题
题目背景
时限1秒,内存512MB
题目描述
猫国的铁路系统中有 nn 个站点,从 1 - n1−n 编号。小猫准备从 11 号站点出发,乘坐列车回到猫窝所在的 nn 号站点。它查询了能够乘坐的列车,这些列车共 mm 班,从1 - m1−m编号。小猫将在 00 时刻到达 11 号站点。对于 ii 号列车,它将在时刻 p_ipi 从站点 x_ixi 出发,在时刻 q_iqi 直达站点 y_iyi,小猫只能在时刻 p_ipi 上 ii 号列车,也只能在时刻 q_iqi 下 ii 号列车。小猫可以通过多次换乘到达 nn 号站点。一次换乘是指对于两班列车,假设分别为 uu号与 vv 号列车,若 y_u = x_vyu=xv 并且 q_u \leq p_vqu≤pv,那么小猫可以乘坐完 uu 号列车后在 y_uyu 号站点等待 p_v - q_upv−qu 个时刻,并在时刻 p_vpv 乘坐 vv 号列车。
小猫只想回到猫窝并且减少途中的麻烦,对此它用烦躁值来衡量。
-
小猫在站点等待时将增加烦躁值,对于一次 t (t \geq 0)t(t≥0) 个时刻的等待,烦躁值将增加 At^2 + Bt + CAt2+Bt+C,其中 A, B,CA,B,C 是给定的常数。注意:小猫登上第一班列车前,即从 00 时刻起停留在 11 号站点的那些时刻也算作一次等待。
-
若小猫最终在时刻 zz 到达 nn 号站点,则烦躁值将再增加 zz。
形式化地说,若小猫共乘坐了 kk 班列车,依次乘坐的列车编号可用序列 s_1, s_2, \cdots , s_ks1,s2,⋯,sk表示。该方案被称作一条可行的回家路线,当且仅当它满足下列两个条件:
-
x_{s1} = 1xs1=1 , y_{sk} = nysk=n
-
对于所有 j (1 \leq j < k)j(1≤j<k),满足 y_{sj} = x_{s_{j+1}}ysj=xsj+1 且 q_{sj}\leq p_{s_{j+1}}qsj≤psj+1
对于该回家路线,小猫得到的烦躁值将为:
q_{s_k}+(A\times p_{s_1}^2+B\times 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)qsk+(A×ps12+B×ps1+C)+j=1∑k−1(A(psj+1−qsj)2+B(psj+1−qsj)+C)
小猫想让自己的烦躁值尽量小,请你帮它求出所有可行的回家路线中,能得到的最 小的烦躁值。题目保证至少存在一条可行的回家路线。
输入输出格式
输入格式:第一行五个整数 n, m, A, B,Cn,m,A,B,C,变量意义见题目描述。
接下来 mm 行,第 ii 行四个整数 x_i, y_i, p_i, q_ixi,yi,pi,qi,分别表示 ii 号列车的出发站、到达站、出发时刻与到达时刻。
输出格式:输出仅一行一个整数,表示所求的答案。
输入输出样例
说明
共有三条可行的回家路线:
- 依次乘坐 1,4 号列车,得到的烦躁值为:10 + (1 \times 3^2 + 5 \times 3 + 10) + (1 \times (9 - 4)^2 + 5 \times (9 - 4) + 10)= 10410+(1×32+5×3+10)+(1×(9−4)2+5×(9−4)+10)=104
- 依次乘坐 2,4 号列车,得到的烦躁值为:10 + (1 \times 5^2 + 5 \times 5 + 10) + (1 \times (9 - 7)^2 + 5 \times (9 - 7) + 10)= 9410+(1×52+5×5+10)+(1×(9−7)2+5×(9−7)+10)=94
- 依次乘坐 3,4 号列车,得到的烦躁值为:10 + (1 \times 6^2 + 5 \times 6 + 10) + (1 \times (9 - 8)^2 + 5 \times (9 - 8) + 10)= 10210+(1×62+5×6+10)+(1×(9−8)2+5×(9−8)+10)=102
第二条路线得到的烦躁值最小为 9494。
#笔试题目#