总体思路就是暴力,我们定义cost[i][j]表示第i天到第j天选择同一道路的花费(对于这个我们用起点跑个dij即可).
好,下一步呢,我们不妨再设置一个状态f[i]表示到了第i天的最小花费是多少.它可以由<=的任何j转移过来.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105,M=25;
struct vv{
    int to,val;
};
ll f[N];
bool vis[M];
ll cost[N][N];//预处理从i到j天走同一道路的mincost.
vector<vv>v[M];
int id[M*M],l[M*M],r[M*M];

ll dis[M];//表示1到i的最短距离.
int n,m,k,e;
int dij()
{
    priority_queue<pair<ll,int> >q;
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    q.push({0,1});
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        ll fi=t.first;int se=t.second;
        if(vis[se]) continue;
        vis[se]=true;
        for(int i=0;i<v[se].size();i++)
        {
            int s=v[se][i].to;
            if(vis[s])  continue;
            int va=v[se][i].val;
            dis[s]=min(dis[se]+va,dis[s]);
            q.push({-dis[s],s});
        }
    }
    return dis[m];
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&e);
    for(int i=1;i<=e;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    int d;scanf("%d",&d);
    for(int i=1;i<=d;i++)   scanf("%d%d%d",&id[i],&l[i],&r[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            memset(vis,false,sizeof vis);
            for(int k=1;k<=d;k++)
            {
                if(!(l[k]>j||r[k]<i))   vis[id[k]]=true;
            }
            cost[i][j]=dij();
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(cost[1][i]<(0x3f3f3f3f))    f[i]=cost[1][i]*i;
        else                           f[i]=1e18;
        for(int j=1;j<=i;j++)
        {
            f[i]=min(f[i],f[j-1]+1ll*(i-j+1)*cost[j][i]+k);
        }
    }
    printf("%lld\n",f[n]);
    return 0;
}