分析

由于数据范围非常小
我们可以有很多大胆的乱搞尝试
Dijkstra + DP
我们不知道哪一天会修改路线
那我们就考虑吧所有的情况算出来
也就是Va[i][j]表示第i天到第j天都使用一套方案的最短路
那么我们就可以直接枚举断点
也就是的暴力DP即可
时间复杂度：
（是因为边数可能会有）

吐槽

洛谷得了一个最优解，牛客始终拿不到，Rank 1那位巨佬%%%

代码

//P1772
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define Skip cout<<endl;
#define INF 0x3f3f3f3f
#define Mod 998244353
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const int MaxN=1e2+10,MaxM=30,MaxP=1e4+10;

int Day,Total,K,Side,u,v,w,Test;
int Next[MaxM*MaxM],End[MaxM*MaxM],Head[MaxM],Cur,Val[MaxM*MaxM];
struct Node { int Opt,From,To; }Line[MaxP];
bool Choose[MaxM],Jud[MaxM];
int Dist[MaxM];
LL DP[MaxN],Va[MaxN][MaxN];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Mine;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline int Read() {
    int Temp=0;
    char Ch=getchar();
    while(Ch>'9' || Ch<'0') { Ch=getchar(); }
    while(Ch>='0' && Ch<='9') { Temp=(Temp<<1)+(Temp<<3)+(Ch ^ 48); Ch=getchar(); }
    return Temp;
}

inline void Add_Edge(int From,int To,int Temp) {
    Next[++Cur]=Head[From];
    Head[From]=Cur;
    End[Cur]=To;
    Val[Cur]=Temp;
}

inline void Dijkstra() {
    Dist[1]=0; 
    Mine.push(make_pair(Dist[1],1));
    while(!Mine.empty()) {
        pair<int,int>New=Mine.top();
        Mine.pop();
        if(Jud[New.second]) continue;
        Jud[New.second]=true;
        for(int i=Head[New.second];i;i=Next[i]) {
            if(!Choose[End[i]]) continue;
            if(New.first+Val[i]<Dist[End[i]]) {
                Dist[End[i]]=New.first+Val[i];
                Mine.push(make_pair(Dist[End[i]],End[i]));
            } 
        }
    }
}

signed main() {
    // File();
    // ios::sync_with_stdio(false);
    Day=Read(); Total=Read(); K=Read(); Side=Read();
    FOR(i,1,Side) { u=Read(); v=Read(); w=Read(); Add_Edge(u,v,w); Add_Edge(v,u,w); }
    Test=Read();
    FOR(i,1,Test) { Line[i].Opt=Read(); Line[i].From=Read(); Line[i].To=Read(); }
    FOR(i,1,Day) FOR(j,i,Day) {
        Cl(Jud,false); Cl(Dist,0x3f); 
        while(!Mine.empty()) Mine.pop();
        Cl(Choose,true);
        FOR(k,1,Test) if(Line[k].From<=j && Line[k].To>=i) { Choose[Line[k].Opt]=false; }
        // Skip;
        // FOR(i,1,Total) cout<<"i: "<<Choose[i]<<endl;
        // Skip;
        Dijkstra();
        Va[i][j]=Dist[Total];       
    }
    Cl(DP,0x3f);
    FOR(i,1,Day) { DP[i]=1ll*Va[1][i]*i; BOR(j,i-1,0) {
        DP[i]=min(DP[i],DP[j]+Va[j+1][i]*(i-j)+K);
    } }
    // FOR(i,1,Day) { FOR(j,i,Day) cout<<"i: "<<i<<" j: "<<j<<" Va: "<<Va[i][j]<<endl; }
    // FOR(i,0,Day) cout<<"i: "<<i<<" DP: "<<DP[i]<<endl;
    printf("%lld\n",DP[Day]);
    // cout<<DP[Day]<<endl;
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}