很明显，这道题要求最短路，如果换路线不要钱的话，我们直接对于每天分别求最短路即可，但可惜的是要钱，那就dp啊
设(f[i])为第一天到第(i)天最小费用，那么(f[i]=min(f[j-1]+(i-j+1)*l+K)(1<=j<=i))，(l)表示第(i)天到第(j)天都可以通行的最短路，由于这道题数据范围奇小，貌似用弗洛伊德求最短路也是能过的
所以看代码吧
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<queue>
#define ll long long
#define gc getchar
using namespace std;
inline ll read(){
ll a=0;int f=0;char p=gc();
while(!isdigit(p)){f|=p=='-';p=gc();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
return f?-a:a;
}int n,m,K,p;
struct ahaha{
int w,to,next;
}e[1000];int tot,head[25];
inline void add(int u,int v,int w){
e[tot]={w,v,head[u]};head[u]=tot++;
}
struct ahaha1{
int d,u;
inline bool friend operator<(const ahaha1 x,const ahaha1 y){
return x.d>y.d;
}
};
priority_queue<ahaha1>q;
int b[25],d[25];
inline int dij(){memset(d,63,sizeof d);
d[1]=0;q.push({0,1});
while(!q.empty()){
ahaha1 a=q.top();q.pop();int u=a.u;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;if(b[v])continue;
if(d[v]>d[u]+e[i].w){
d[v]=d[u]+e[i].w;
q.push({d[v],v});
}
}
}
return d[m];
}
int f[105],c[25][105];
int main(){memset(head,-1,sizeof head);
n=read();m=read();K=read();p=read();
while(p--){
int u=read(),v=read(),w=read();
add(u,v,w);add(v,u,w);
}
p=read();
while(p--){
int a=read(),l=read(),r=read();
for(int j=l;j<=r;++j)
c[a][j]=1;
}
memset(f,63,sizeof f);f[0]=-K;
for(int i=1;i<=n;++i){
memset(b,0,sizeof b);
for(int j=i;j;--j){
for(int k=1;k<=m;++k)
if(c[k][j])b[k]=1;
int di=dij();
if(di>10000000)break;
f[i]=min(f[i],f[j-1]+(i-j+1)*di+K);
}
}
printf("%d
",f[n]);
return 0;
}