根据题意打好标记后跑spfa，然后dp
#include <stdio.h> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <vector> using namespace std; const int maxm=20+10; const int maxn=100+10; const int maxe=1000+10; struct hh { int u,v,w,next; }E[maxe]; int n,m,k,e,d,point; int dis[maxm],vis[maxm],head[maxm],flag[maxn][maxm]; long long cost[maxn][maxn],f[maxn]; template <class T> void read(T&x) { x=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); } int spfa(int a,int b) { int pt[maxm]; queue<int>q; memset(vis,0,sizeof(vis)); memset(dis,0x7f/3,sizeof(dis)); memset(pt,0,sizeof(pt)); vis[1]=1;q.push(1);dis[1]=0; for(register int i=a;i<=b;i++) for(register int j=1;j<=m;j++) if(flag[i][j])pt[j]=1; while(!q.empty()) { int x=q.front();q.pop();vis[x]=0; for(register int i=head[x];i!=-1;i=E[i].next) { int y=E[i].v; if(!pt[y]&&dis[y]>dis[x]+E[i].w) { dis[y]=dis[x]+E[i].w; if(!vis[y]){vis[y]=1;q.push(y);} } } } return dis[m]; } void add(int u,int v,int w) { E[++point].u=u;E[point].v=v;E[point].w=w;E[point].next=head[u];head[u]=point; E[++point].u=v;E[point].v=u;E[point].w=w;E[point].next=head[v];head[v]=point; } int main() { memset(head,-1,sizeof(head)); read(n);read(m);read(k);read(e); int u,v,w; for(register int i=1;i<=e;i++) { read(u);read(v);read(w); add(u,v,w); } read(d); int p,a,b; for(register int i=1;i<=d;i++) { read(p);read(a);read(b); for(register int j=a;j<=b;j++)flag[j][p]=1; } for(register int i=1;i<=n;i++) for(register int j=1;j<=n;j++) cost[i][j]=spfa(i,j); for(register int i=1;i<=n;i++) { f[i]=(long long)cost[1][i]*i; for(int j=1;j<=i;j++) f[i]=min(f[i],f[j]+k+cost[j+1][i]*(i-j)); } printf("%lld",f[n]); return 0; }