题面

很明显，这道题要求最短路，如果换路线不要钱的话，我们直接对于每天分别求最短路即可，但可惜的是要钱，那就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\n",f[n]);
    return 0;
}