http://www.lydsy.com/JudgeOnline/problem.php?id=1003 https://www.luogu.org/problem/show?pid=1772 DP+最短路 因为在某一区间段时间内有码头会暂时关闭，所以我们可以求出t1~t2时间段里从1到m的最短路（在这个时间段里无论何时某码头关闭，那么整个时间段都不能经过这个码头）
接下来交给DP： 定义状态：f[i]表示前i个时间运输所用的最小代价，那么状态转移方程就很好得出了：
k表示改动一次航线的代价，d[i][j]表示i~j时间段从1~m的最短路 答案就是f[n]； 初始化：f[i]=d[1][i]; 上代码：
#include<bits/stdc++.h> #define ll long long using namespace std; const ll oo=1e9; ll nedge=0,p[100001],c[100001],head[100001],nex[100001]; ll d[101][101],q[1000001],dist[10001]; ll n,m,k,e,f[1001]; bool vis[1001],mdzz[1001],jzq[101][101]={0}; inline void addedge(ll x,ll y,ll z){ p[++nedge]=y;c[nedge]=z; nex[nedge]=head[x];head[x]=nedge; } inline ll spfa(ll le,ll re){ for(ll i=1;i<=m;i++)dist[i]=oo; memset(vis,0,sizeof vis); memset(mdzz,0,sizeof mdzz); for(ll i=1;i<=m;i++) for(ll j=le;j<=re;j++)if(jzq[i][j]){mdzz[i]=1;break;} dist[1]=0;vis[1]=true;q[1]=1; ll l=1,r=1; while(l<=r){ ll now=q[l]; ll k=head[now]; while(k>0){ if(!mdzz[p[k]]&&dist[p[k]]>dist[now]+c[k]){ dist[p[k]]=dist[now]+c[k]; if(!vis[p[k]]){ r++; q[r]=p[k]; vis[p[k]]=true; } } k=nex[k]; } vis[now]=false; l++; } return dist[m]; } int main() { scanf("%lld%lld%lld%lld",&n,&m,&k,&e); for(ll i=1;i<=e;i++){ ll x,y,z;scanf("%lld%lld%lld",&x,&y,&z); addedge(x,y,z); addedge(y,x,z); } ll t;scanf("%lld",&t); for(ll i=1;i<=t;i++){ ll x,y,z;scanf("%lld%lld%lld",&x,&y,&z); for(ll j=y;j<=z;j++)jzq[x][j]=1; } for(ll i=1;i<=n;i++) for(ll j=i;j<=n;j++)d[i][j]=spfa(i,j); for(ll i=1;i<=n;i++){ f[i]=d[1][i]*i; for(ll j=1;j<i;j++)f[i]=min(f[i],f[j]+k+(i-j)*d[j+1][i]); } printf("%lld",f[n]); return 0; }