站外题

20241015D

题目描述

俨俨是一只超帅的烟灰色缅因库恩猫。

缅因库恩猫是运动量巨大的一种猫。为了消耗俨俨的体力，主人给俨俨买了一个可拆卸猫爬架。猫爬架上共有 $m$ 个停靠点，$1$ 号停靠点是地面，$m$ 号停靠点是猫爬架的顶端。

俨俨可以从一个停靠点跳到另一个停靠点（反之自然也可以），但是究竟怎样的两个停靠点可以让俨俨跳跃是没有规律的。不过好在主人根据观察和定量计算，知道了每一对可以互相跳过去的停靠点，而且知道了跳过每一对停靠点对于俨俨精力值的消耗。

俨俨每天都要从地面跳到猫爬架的顶端，为了增大俨俨的运动量，主人会在某些时间段限制一些停靠点不能停靠，来改变俨俨的路线。对于俨俨而言，如果某天跳跃的路线和前一天不同，则需要固定消耗 $k$ 点精力来改变路线。

俨俨现在知道每一个停靠点会在哪些天被限制不能停靠，他想知道自己最少消耗多少精力呢？

输入格式

输入文件为 cat.in

第一行是四个整数 $n, m, k, e$。$n$表示天数，$m$表示猫爬架上停靠点的总数， $k$表示每次改变路线消耗的精力， $e$表示俨俨能够跳跃的停靠点对的个数。

接下来$e$行每行是一对停靠点的描述，包括了三个整数，$x,y,z$。表示俨俨可以在$x$号和$y$号停靠点之间跳跃，跳跃一次花费的精力为$z$。

再接下来一行是一个整数 $d$，后面的 $d$ 行每行是三个整数 $p, a, b$ 。表示编号为 $p$ 的停靠点在 $[a, b]$ 天之间被禁止停靠。同一个停靠点有可能在多个时间段内被禁止。但任何时间都存在至少一条路线能够让俨俨完成任务。

输出格式

输出文件为 cat.out

输出包括了一个整数表示最小的总精力消耗。

总精力消耗为跳跃消耗的精力和改变路线消耗的精力的和。

样例输入 #1

5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5

样例输出 #1

32

数据范围

对于 $100\%$ 的数据，$1 \le n \le 100$，$1\le m \le 20$, $1 \le k \le 500$, $1 \le e \le 200$。

样例说明

前三天走 $1 \to 4 \to 5$，后两天走 $1 \to 3 \to 5$，这样总成本为 $(2+2)\times 3+(3+2)\times 2+10=32$。

为啥会炸内存啊qwq

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,p,t,x,y,z,prestk,totans=0x3f3f3f3f3f3f3f3f;
long long lnph[114][514];
long long dp[104];
long long gs[104];//限行路段 
long long head[22],e[403],w[403],nxt[403],idx;
void add(long long u,long long v,long long s){
	e[idx]=v;
	w[idx]=s;
	nxt[idx]=head[u];
	head[u]=idx;
	idx++;
	return;
}
long long vis;
long long dijkstra(long long u,long long st){
	vis=0;
	long long path[22];
	long long mn,tmp;
	memset(path,63,sizeof(path));
	path[1]=0;
	for(long long i=1;i<=m;i++){
		mn=0x3f3f3f3f3f3f3f3f;
		for(long long ii=1;ii<=m;ii++){
			if(vis&(1<<ii)==0&&st&(1<<ii)==0){
				if(path[ii]<mn){
					mn=path[ii];
					tmp=ii;
				}
			}
		}
		vis|=(1<<tmp);
		for(long long ii=head[tmp];ii!=-1;ii=nxt[ii]){
			if(vis&(1<<e[ii]))continue;
			if(st&(1<<e[ii]))continue;
			path[e[ii]]=max(path[e[ii]],path[tmp]+w[ii]);
		}
	}
	return path[m];
}
int main(){
	memset(dp,63,sizeof(dp));
	memset(head,-1,sizeof(head));
	scanf("%lld %lld %lld %lld",&n,&m,&k,&p);
	for(long long i=1;i<=p;i++){
		scanf("%lld %lld %lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	scanf("%lld",&t);
	for(long long i=1;i<=t;i++){
		scanf("%lld %lld %lld",&x,&y,&z);
		for(long long ii=y;ii<=z;ii++)gs[ii]|=(1<<x);
	}
	for(long long i=1;i<=n;i++){
		prestk=0;//这几天有哪些路段限行 
		for(long long ii=i;ii<=n;ii++){
			prestk|=gs[ii];
			lnph[i][ii]=dijkstra(1,prestk);
		}
	}
	dp[0]=-k;
	for(long long i=1;i<=n;i++)for(long long ii=0;ii<i;ii++)dp[i]=min(dp[i],dp[ii]+lnph[ii+1][i]*(i-ii)+k);
	printf("%lld",dp[n]);
	return 0;
}