[NOI2019]回家路线

傷城~ 2021-10-23 18:50 337阅读 0赞

# \[NOI2019\]回家路线 #

## 题目大意： ##

有\\(n\\)个站点，\\(m\\)趟车，每趟车在\\(p\_i\\)时从\\(x\_i\\)出发，\\(q\_i\\)时到达\\(y\_i\\)。

若小猫共乘坐了\\(k\\)班列车，依次乘坐的列车编号可用序列\\(s\_\{1\\sim 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\\le 10^5,m\\le2\\times10^5,1\\le p\_i<q\_i\\le 1000\\)

## 思路： ##

将所有车按照\\(p\_i\\)排序，枚举每趟车，枚举到达\\(p\_i\\)的时间。

\\(f\[i\]\[j\]+i\\)表示时间\\(j\\)到达\\(i\\)车站最小烦躁值。

时间复杂度\\(\\mathcal O(m\\cdot q)\\)。

## 源代码： ##

#include<cstdio> #include<cctype> #include<climits> #include<algorithm> inline int getint() { register char ch; while(!isdigit(ch=getchar())); register int x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return x; } const int N=1e5+1,M=2e5+1,T=1e3+1; int n,m,A,B,C,f[N][T]; struct Edge { int u,v,p,q; bool operator < (const Edge &rhs) const { return p<rhs.p; } }; Edge e[M]; inline int calc(const int &x) { return A*x*x+B*x+C; } inline void upd(int &a,const int &b) { a=std::min(a,b); } int main() { freopen("route.in","r",stdin); freopen("route.out","w",stdout); n=getint(),m=getint(); A=getint(),B=getint(),C=getint(); for(register int i=1;i<=m;i++) { const int u=getint(),v=getint(),p=getint(),q=getint(); e[i]=(Edge){u,v,p,q}; } for(register int i=1;i<=n;i++) { std::fill(&f[i][0],&f[i][T],INT_MAX); } f[1][0]=0; std::sort(&e[1],&e[m]+1); for(register int i=1;i<=m;i++) { for(register int j=0;j<=e[i].p;j++) { if(f[e[i].u][j]==INT_MAX) continue; upd(f[e[i].v][e[i].q],f[e[i].u][j]+calc(e[i].p-j)); } } int ans=INT_MAX; for(register int i=0;i<T;i++) { if(f[n][i]!=INT_MAX) upd(ans,f[n][i]+i); } printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/skylee03/p/11196705.html