BZOJ1003 [ZJOI2006]物流运输trans 【动态规划+最短路】

tonyfang posted @ 2015年8月23日 21:30 in BZOJ with tags c++ OI , 481 阅读

很容易想到$DP$来做,那么$f[i]$表示到第$i$天所需要的最小费用。

那么很容易得到

$f[i]=min(spfa(1,i), f[j]+spfa(j+1,i)+k (2 \leq j \leq i-1))$

转移表示的就是改变路线的时间点。

spfa的时候维护一下哪些不能被访问到就行了。

复杂度$O(kn^{2}e)$,极限$O(kn^{3}e)$,用$Dijkstra$可以稳定在$O(ken^{2}logn)$。对于这题小数据都可以过。

代码:($spfa$)

 

# include <stdio.h>
# include <string.h>
# include <queue>
using namespace std;
const int Max=1010,INF=1000000000;
int n,m,k,e,head[Max],next[Max],to[Max],w[Max],tot=0,dd,ca[Max],cb[Max],cc[Max],f[Max];
int d[Max];bool vis[Max];
inline void add(int u,int v,int _w) {next[++tot]=head[u];head[u]=tot;to[tot]=v;w[tot]=_w;}
bool cantvis[Max];queue<int> q;
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b) {return a<b?a:b;}
inline void qc() {while(!q.empty()) q.pop();}
inline int spfa(int timea,int timeb) {
	memset(cantvis,0,sizeof(cantvis));
	qc();for (int i=1;i<=m;++i) d[i]=INF; 
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=dd;++i) if(max(timea,ca[i])<=min(timeb,cb[i])) cantvis[cc[i]]=1;
	q.push(1);vis[1]=1;d[1]=0;
	while(!q.empty()) {
		int top=q.front();q.pop();
		vis[top]=0;
		for (int i=head[top];i;i=next[i]) {
			if(cantvis[to[i]]) continue;
			if(d[top]+w[i]<d[to[i]]) {
				d[to[i]]=d[top]+w[i];
				if(!vis[to[i]]) {
					vis[to[i]]=1;
					q.push(to[i]);	
				}
			}
		}
	}
	if(d[m]==INF) return INF;
	else return d[m]*(timeb-timea+1);
}
int main() {
	scanf("%d%d%d%d",&n,&m,&k,&e);
	for (int i=1,u,v,_w;i<=e;++i) {
		scanf("%d%d%d",&u,&v,&_w);
		add(u,v,_w);
		add(v,u,_w);
	}
	scanf("%d",&dd);
	for (int i=1;i<=dd;++i)
		scanf("%d%d%d",&cc[i],&ca[i],&cb[i]);
	for (int i=1;i<=n;++i) {
		f[i]=spfa(1,i);
		for (int j=2;j<i;++j) {
			int co=spfa(j+1,i);
			if(co==INF) continue;
			else f[i]=min(f[i],f[j]+co+k);
		}
	}
	printf("%d\n",f[n]);
	return 0;
}
पिछले-प्रश्न-पत्र.co 说:
2023年4月28日 15:37

Hindi Model Question Papers Bihar School 10th Exam Board BSEB, Bihar Board 10th Class Model Papers 2023 Matric Exam Pattern, BSEB Patna Board Matric 10th Model Papers 2023 Sample Questions, Bihar Board 10th Model Papers 2023 Download, पिछले-प्रश्न-पत्र.com BSEB Matric Bihar matric model paper 2023 bseb 10th sample paper 2023, bihar board 10th model paper 2023 pdf, bihar board 10th class model test paper 2023, bseb matric previous sample paper class 10th bihar board model question paper, bseb matric model question paper 2023.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter