很容易想到$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;
}