分析

我们可以对于每一天考虑，如果有一天改了道，那么贪心的选择也应该是最短路，而不是其它的路径。这个还是比较显然的。那么现在考虑一个线性 。令 表示考虑 从第 天的最小代价和。那么转移为 。这里引入了一个 的数组。这里表示从第 天到第 天的合法的最短路。那么我们可以先预处理 总的复杂度为 。最后 的复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 201;
#define LL long long
const int inf = 0x3f3f3f3f;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f?-x:x;
}
#define piiL pair<LL,int>
#define piii pair<int,int>
LL f[N];
int g[N][N],dis[21];
int L[N],R[N],id[N],n,m,K,E;
bool vis[21];
vector<piii>G[N];
priority_queue<piiL> q;
void solve(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;q.push(piiL(dis[s],s));while(!q.empty()){
        int x=q.top().second;q.pop();if(vis[x])continue;vis[x]=1;
        for(auto e:G[x]) {if(vis[e.first] || dis[e.first]<=dis[x]+e.second) continue;
            dis[e.first]=dis[x]+e.second;q.push(piiL(-dis[e.first],e.first));
        }
    }
}
int main() {
    n=read();m=read();K=read();E=read();
    for(int i=1,a,b,c;i<=E;i++){
        a=read();b=read();c=read();
        G[a].push_back(piii(b,c));G[b].push_back(piii(a,c));
    }
    int T=read();for(int i=1;i<=T;i++)id[i]=read(),L[i]=read(),R[i]=read();
    f[0]=0;
    for(int l=1;l<=n;l++){
        for(int r=l;r<=n;r++){
            memset(vis,0,sizeof(vis));
            for(int k=1;k<=T;k++) if(!(r<L[k]||l>R[k]))vis[id[k]]=1;
            solve(1);g[l][r]=dis[m];
        }
    }
    for(int i=1;i<=n;i++){
        if(g[1][i]<inf)f[i]=g[1][i]*i;
        else f[i]=1e18;
        for(int j=1;j<=i;j++){
            if(g[j][i]<inf)f[i]=min(f[i],f[j-1]+g[j][i]*(i-j+1)+K);
        }
    }
    cout<<f[n]<<endl;
}