基本思路：dfs 处理出所有的能使 $1,n$ 连通的点集及经过点集的最短路径。

设 $f(i,st)$ 表示 前 $i$ 天，第 $i$ 天经过路径点集为 $st$ (状压) 的最小代价。

方程 $f(i,st)=\begin{cases}f(i-1,st)+cost_{st} & st\text{合法且是昨天的最优解}\\ \min\{\,f(i-1,st),lst+k\,\}+cost_{st} & st\text{合法且不是昨天的最优解}\\ inf & st\text{中有点被关闭}\end{cases}$

$cost$ 是路径点集的最短路，$lst$ 是 $i-1$ 天的最优解。

然后发现前两个情况能合并，再加上滚动数组。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=200,M=21;
const ll INF=0x3f3f3f3f3f3f3f3f;

int n,m,k,e;
ll adm[N][N];

ll cost[(1<<M-1)+10];//记忆化一下，方便优化
vector<int> road;
int vis[N];

void dfs(int x,ll len,int sta)
{
	if(len>=cost[sta]) return;//剪枝
	cost[sta]=len;
	if(x==n) {road.push_back(sta); return ;}//边界，统计所有合法路径
	for(int i=2;i<=m;i++)
	{
		if(adm[x][i]<0x3f3f3f3f&&!vis[i])
		{
			vis[i]=1;
			dfs(i,len+adm[x][i],sta|(1<<i-1));
			vis[i]=0;
		}
	}
}

int cls[N];//每天的港口关闭情况
ll f[3][1<<(M-1)];//滚动，不滚动必MLE

int main()
{
	scanf("%d%d%d%d",&n,&m,&k,&e);
	memset(adm,0x3f,sizeof adm);
	for(int i=1;i<=e;i++)
	{
		int x,y;ll w;
		scanf("%d%d%lld",&x,&y,&w);
		adm[x][y]=adm[y][x]=min(adm[x][y],w);
	}
	int d;
	scanf("%d",&d);
	for(int i=1;i<=d;i++)
	{
		int p,a,b;
		scanf("%d%d%d",&p,&a,&b);
		for(int j=a;j<=b;j++)//记录每天的关闭情况
			cls[j]|=1<<(p-1);
	}
	memset(cost,0x3f,sizeof cost);
	memset(f,0,sizeof f);
	vis[1]=1; dfs(1,0,1);
	ll yst=0;
	for(int i=1;i<=n;i++)
	{
		int t=i&1;ll tod=INF;
		for(int j=0;j<road.size();j++)
		{
			int sta=road[j];
			if(sta&cls[i]) {f[t][sta]=INF; continue;}
			f[t][sta]=min(f[t^1][sta],yst+k)+cost[sta];
			tod=min(f[t][sta],tod);
		}
		yst=tod;
	}
	printf("%lld",yst);
	return 0;
}