对于本题我们设ext[i][j]计算第i个码头在前j天总共有几天不能用（其实就一前缀和），设dis[i][j]是从第i天到第j天不变运输路线的最短路径，设f[i]是前i天运输货物的最小花费。
然后n2*O（spfa）处理出整个dis数组。判断一个码头a从第i天到第j天能不能用的方法是ext[a][j]-ext[a][i-1]，如果该数等于0，则说明这几天没有一天不能用，则spfa的时候可以扩展到该码头；否则至少有一天不能用，spfa的时候也就不能扩展。
接着f[i]=min(f[i],f[j]+dis[j+1][i]*(i-j)+k) 其中i-j是天数，j是枚举的从哪天开始换路线。
最后f[n]即是答案。
放上代码
#include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<cctype> #include<algorithm> inline int read(){ int num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } using namespace std; queue <int> q; bool vis[100200]; int dst[1500]; int dis[150][150]; int n,m,o,e; int ext[30][150]; struct Edge{ int next,to,val; }edge[1000200]; int head[12000],num; inline void add(int from,int to,int val){ edge[++num]=(Edge){head[from],to,val}; head[from]=num; } void Spfa(int s,int t){ q.push(1);memset(dst,127/3,sizeof(dst));dst[1]=0; while(!q.empty()){ int from=q.front(); q.pop();vis[from]=0; for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(ext[to][t]-ext[to][s-1]>0) continue; if(dst[to]>dst[from]+edge[i].val){ dst[to]=dst[from]+edge[i].val; if(vis[to]) continue; q.push(to); vis[to]=1; } } } dis[s][t]=dst[m]; } long long f[2000]; int main(){ memset(f,127/3,sizeof(f));memset(dis,127/3,sizeof(dis)); n=read(),m=read(),o=read(),e=read(); f[0]=-o; for(int i=1;i<=e;++i){ int from=read(),to=read(),val=read(); add(from,to,val); add(to,from,val); } int T=read(); for(int i=1;i<=T;++i){ int x=read(),a=read(),b=read(); for(int j=a;j<=b;++j) ext[x][j]=1; } for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) ext[i][j]+=ext[i][j-1]; for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) Spfa(i,j); for(int i=1;i<=n;++i) for(int j=0;j<i;++j){ if(dis[j+1][i]==dis[0][0]) continue; f[i]=min(f[i],f[j]+dis[j+1][i]*(i-j)+o); } printf("%d",f[n]); return 0; }