[NOI2019]回家路线

题目大意：

有\(n\)个站点，\(m\)趟车，每趟车在\(p_i\)时从\(x_i\)出发，\(q_i\)时到达\(y_i\)。

若小猫共乘坐了\(k\)班列车，依次乘坐的列车编号可用序列\(s_{1\sim k}\)表示。该方案被称作一条可行的回家路线，当且仅当它满足下列两个条件：

\(x_{s_1}=1,y_{s_k}=n\)；
对于所有\(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;

}

巴特西

[NOI2019]回家路线

[NOI2019]回家路线

题目大意：

思路：

源代码：

最新文章

热门文章