自助建站系统哪个好,微信公众平台官方,淘宝网页制作教程视频,wordpress评论自定义题目描述
猫国的铁路系统中有 nn 个站点#xff0c;从 1 - n1−n 编号。小猫准备从 11 号站点出发#xff0c;乘坐列车回到猫窝所在的 nn 号站点。它查询了能够乘坐的列车#xff0c;这些列车共 mm 班#xff0c;从1 - m1−m编号。小猫将在 00 时刻到达 11 号站点。对于 i…题目描述
猫国的铁路系统中有 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_vyuxv 并且 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 CAt2BtC其中 A, B,CA,B,C 是给定的常数。注意小猫登上第一班列车前即从 00 时刻起停留在 11 号站点的那些时刻也算作一次等待。若小猫最终在时刻 zz 到达 nn 号站点则烦躁值将再增加 zz。
形式化地说若小猫共乘坐了 kk 班列车依次乘坐的列车编号可用序列 s_1, s_2, \cdots , s_ks1,s2,⋯,sk表示。该方案被称作一条可行的回家路线当且仅当它满足下列两个条件
x_{s1} 1xs11 , y_{sk} nyskn对于所有 j (1 \leq j k)j(1≤jk)满足 y_{sj} x_{s_{j1}}ysjxsj1 且 q_{sj}\leq p_{s_{j1}}qsj≤psj1
对于该回家路线小猫得到的烦躁值将为
q_{s_k}(A\times p_{s_1}^2B\times p_{s_1}C)\sum_{j1}^{k-1}(A(p_{s_{j1}}-q_{s_j})^2B(p_{s_{j1}}-q_{s_j})C)qsk(A×ps12B×ps1C)j1∑k−1(A(psj1−qsj)2B(psj1−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
样例输入 #1
3 4 1 5 10
1 2 3 4
1 2 5 7
1 2 6 8
2 3 9 10Copy
样例输出 #1
94Copy
样例 #2
样例输入 #2
4 3 1 2 3
1 2 2 3
2 3 5 7
3 4 7 9Copy
样例输出 #2
34Copy
提示
更多样例
您可以通过附加文件获得更多样例。
样例 3
见附加文件的 route/route3.in 与 route/route3.ans。
该样例的数据类型与最终测试点 5 \sim 85∼8 一致。
样例 4
见附加文件的 route/route4.in 与 route/route4.ans。
该样例的数据类型与最终测试点 11 \sim 1411∼14 一致。
样例 5
见附加文件的 route/route5.in 与 route/route5.ans。
该样例的数据类型与最终测试点 18 \sim 2018∼20 一致。
样例 1 解释
共有三条可行的回家路线
依次乘坐 14 号列车得到的烦躁值为10 (1 \times 3^2 5 \times 3 10) (1 \times (9 - 4)^2 5 \times (9 - 4) 10) 10410(1×325×310)(1×(9−4)25×(9−4)10)104依次乘坐 24 号列车得到的烦躁值为10 (1 \times 5^2 5 \times 5 10) (1 \times (9 - 7)^2 5 \times (9 - 7) 10) 9410(1×525×510)(1×(9−7)25×(9−7)10)94依次乘坐 34 号列车得到的烦躁值为10 (1 \times 6^2 5 \times 6 10) (1 \times (9 - 8)^2 5 \times (9 - 8) 10) 10210(1×625×610)(1×(9−8)25×(9−8)10)102
第二条路线得到的烦躁值最小为 9494。
数据范围
对于所有测试点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 \neq y_i , 0 \le p_i q_i \le 10^32≤n≤105,1≤m≤2×105,0≤A≤10,0≤B,C≤106,1≤xi,yi≤n,xiyi,0≤piqi≤103。
每个测试点的具体限制见下表
测试点编号nnmmA,B,CA,B,C 的特殊限制其他特殊条件1\sim 21∼2\le 100≤100n-1n−1无y_ix_i1yixi13\sim 43∼4\le 100≤100ABC0ABC05\sim 85∼8\le 2\times 10^3≤2×103\le 4\times 10^3≤4×103 $x_i 代码:
#include bits/stdc.h
#define N 200005
#define ll long long
#define db double
#define getchar nc
using namespace std;
inline char nc(){static char buf[100000],*p1buf,*p2buf;return p1p2(p2(p1buf)fread(buf,1,100000,stdin),p1p2)?EOF:*p1;
}
inline int read()
{register int x0,f1;register char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9)x(x3)(x1)ch-0,chgetchar();return x*f;
}
inline void write(register ll x)
{if(!x)putchar(0);if(x0)x-x,putchar(-);static int sta[20];register int tot0;while(x)sta[tot]x%10,x/10;while(tot)putchar(sta[--tot]48);
}
inline int Max(register int a,register int b)
{return ab?a:b;
}
inline ll Min(register ll a,register ll b)
{return ab?a:b;
}
struct node{ll x,y;int id;
};
int n,m,A,B,C,maxT0;
int x[N],y[N],p[N],q[N],head[N];
ll ans1926081700000000ll,dp[N];
vectorint d[1005];
vectornodeque[N];
queueint res[1005];
inline db gslope(register node a,register node b)
{return 1.0*(a.y-b.y)/(1.0*(a.x-b.x));
}
inline void ins(register int id)
{int posy[id];node now(node){q[id],dp[id]A*q[id]*q[id]-B*q[id],id};while(que[pos].size()-head[pos]2){int lenque[pos].size();if(gslope(que[pos][len-1],que[pos][len-2])gslope(que[pos][len-2],now))break;que[pos].pop_back();}que[pos].push_back(now);
}
inline void del(register db slpe,register int pos)
{while(que[pos].size()-head[pos]2){if(gslope(que[pos][head[pos]],que[pos][head[pos]1])slpe)return;head[pos];}
}
int main()
{nread(),mread(),Aread(),Bread(),Cread();for(register int i1;im;i)x[i]read(),y[i]read(),p[i]read(),q[i]read(),maxTMax(maxT,q[i]);for(register int i1;im;i)d[p[i]].push_back(i);que[1].push_back((node){0,0,0});for(register int t0;tmaxT;t){while(!res[t].empty())ins(res[t].front()),res[t].pop();int lend[t].size();for(register int k0;klen;k){int idd[t][k];int posx[id];if(que[pos].size()head[pos])continue;db slpe2.0*A*p[id];del(slpe,pos);int jque[pos][head[pos]].id;dp[id]dp[j]1ll*A*(p[id]-q[j])*(p[id]-q[j])1ll*B*(p[id]-q[j])C;res[q[id]].push(id);if(y[id]n)ansMin(ans,dp[id]q[id]);}}write(ans);return 0;
}
