BZOJ1003 物流运输 题解

发现\(n,m\)很小，我们可以先把任意\(2\)天的最短路都给求出来，考虑\(DP\)，设\(f[i][j]\)表示\(j+1\)~ \(i\)这几天内走的是最短路线的最优方案，显然最优情况下\(j+1\)~ \(i\)天走的是同一条路。

#include <bits/stdc++.h>

#define int long long

int n,m,k,E,N;

int head[1000000],tot;

int r[111];

int cn[111][111];

int dis[1000000];

int min[111][111];

std::queue<int>q;

struct edge{

	int to,nxt,w;

}e[1000000];

void add(int x,int y,int z){

	e[++tot]={y,head[x],z};

	head[x]=tot;

}

void D(int d1,int d2){

	for(int i=1;i<=m;++i)dis[i]=1e14;

	dis[1]=0;

	q.push(1);

	while(!q.empty()){

		int x=q.front();

		q.pop();

	  for(int i=head[x],y,f;i;i=e[i].nxt){

	  	y=e[i].to;f=0;

	  	for(int j=d1;j<=d2;++j)f|=cn[y][j];

	  	if(f)continue;

	  	if(dis[y]>dis[x]+e[i].w){

	  	  dis[y]=dis[x]+e[i].w;

	  	  q.push(y);

	  	}

	  }

	}

	min[d1][d2]=dis[m];

}

main(){

	scanf("%lld%lld%lld%lld",&n,&m,&k,&E);

	for(int i=1,x,y,z;i<=E;++i){

		scanf("%lld%lld%lld",&x,&y,&z);

		add(x,y,z);

		add(y,x,z);

	}

	scanf("%lld",&N);

	for(int i=1,x,y,z;i<=N;++i){

		scanf("%lld%lld%lld",&x,&y,&z);

		for(int j=y;j<=z;++j)

		  cn[x][j]=1;

	}

	for(int i=0;i<=n;++i)

	  for(int j=i;j<=n;++j)

	    D(i,j);

  r[0]=0LL;

  for(int i=1;i<=n;++i)r[i]=1e14;

	for(int i=1;i<=n;++i)

	  for(int j=0;j<i;++j)

	    r[i]=std::min(r[i],r[j]+k*(j>0)+min[j+1][i]*(i-j));

	printf("%lld\n",r[n]);

	return 0;

}