Jisoo

思路比较显然的dp

我们怎么走？状压一波

当然可以，但是也不用

$f_{i}$表示第i天的最小花费，显然我们只要枚举上一个转换点就可以了

毕竟转换了之后，之前怎么走的就不重要了

然后spfa预处理一波

#include<iostream> 
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
int all[200][30];
int n,m,k,ee;
int x,y,z;
int head[300];
int p;
int dis[200];
int co[200][200];
int f[200];
struct e{
    int to;
    int ne;
    int v;
}ed[5000];
void add(int f,int to,int v){
    p++;
    ed[p].to=to;
    ed[p].ne=head[f];
    ed[p].v=v;  
    head[f]=p;
}
int d;
int vis[10001];
int ex[100001];
queue<int> q;
void spfa(int l,int r){
    memset(dis,0x3f,sizeof(dis));
    memset(ex,0,sizeof(ex));
    dis[1]=0;
    q.push(1);
    ex[1]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        ex[x]=0;
        for(int i=head[x];i;i=ed[i].ne){
            int v=ed[i].to;
            if(vis[v]) continue;
            if(dis[v]>dis[x]+ed[i].v){
                dis[v]=dis[x]+ed[i].v;
                if(!ex[v]){
                    q.push(v);
                    ex[v]=1;
                }
            }
        }
    }
    co[l][r]=dis[m];
}
signed main(){
    scanf("%d%d%d%d",&n,&m,&k,&ee);
    for(int i=1;i<=ee;++i){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    scanf("%d",&d);
    for(int i=1;i<=d;++i){
        scanf("%d%d%d",&x,&y,&z);
        for(int j=y;j<=z;++j){
            all[j][x]=1;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=i;j<=n;++j){
            memset(vis,0,sizeof(vis));
            for(int z=1;z<=m;++z){
                for(int k=i;k<=j;++k){
                    if(all[k][z]){
                        vis[z]=1;
                        break;
                    }
                }
            }
            spfa(i,j);
        }   
    }
    memset(f,0x7f,sizeof(f));
    f[0]=-k;
    for(int i=1;i<=n;++i){
        for(int j=i-1;j>=0;--j){
            if(co[j+1][i]>=1000000) continue;
            f[i]=min(f[i],f[j]+(i-j)*co[j+1][i]+k);
        }
    }
    cout<<f[n];
    return 0;
}