题目链接：https://www.luogu.com.cn/problem/P1772
洛谷：
时间限制1.00s
内存限制125.00MB
BZOJ：
Time Limit: 10 Sec Memory Limit: 162 MB
Description
物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转
停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种
因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是
修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本
尽可能地小。
Input
第一行是四个整数n（1<=n<=100）、m（1<=m<=20）、K和e。n表示货物运输所需天数，m表示码头总数，K表示
每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编
号以及航线长度（>0）。其中码头A编号为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下来
一行是一个整数d，后面的d行每行是三个整数P（ 1 < P < m）、a、b（1< = a < = b < = n）。表示编号为P的码
头从第a天到第b天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一
条从码头A到码头B的运输路线。
Output
包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。
Sample Input
5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5
Sample Output
32
//前三天走1-4-5，后两天走1-3-5，这样总成本为(2+2)*3+(3+2)*2+10=32
//前三天走1-4-5，后两天走1-3-5，这样总成本为(2+2)*3+(3+2)*2+10=32
首先要读懂题。。。题目的意思是每一天都会有船从1到m，n天就要跑n次1到m。
由于这题的数据比较小，所以解法其实挺暴力的，涉及到最小成本，我们应该可以想到DP，那么一dp[i]代表前i天的最小成本，那么dp方程式应该可以列出来了：
dp[i]=min{dp[i],dp[j-1]+(i-j+1)*dis[m]+k};
其大概意思就是从第j天开始改变航线，那么当前的最小代价就是前j-1天的最小代价加上第j天到第i天的时间乘上1到m的最短距离+k。
那么接下来的关键就是这么保证第j天到第i天可以走通了。其实挺暴力的，我们直接用二维数组暴力打标记就好了：
for (int i=1; i<=d; i++){ int p,l,r; in(p);in(l);in(r); for (int j=l; j<=r; j++) pot[p][j]=true; }
打上标记后就是跑背包了套最短路了：
for (int i=0; i<=n; i++) dp[i]=inf; dp[0]=-k; for (int i=1; i<=n; i++) { memset(distry,false,sizeof distry); for (int j=i; j>=1; j--) { for (int k=1; k<=m; k++) if (pot[k][j]) distry[k]=true; dij(n,m); if (dis[m]==inf) break; dp[i]=min(dp[i],dp[j-1]+(i-j+1)*dis[m]+k); } }
为了保证j到i的路线是可行的，那么我们可以从后往前推，一旦不行就代表这之前的都不行了，可以直接break了，然后就是跑dij最短路了，记得判断的时候加个特判distry数组的存在性。然后就是滚动数组跑一波完事了。
以下是AC代码：
#include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define ll long long const int mac=200; const int inf=1e9+10; struct node { int to,next,w; }eg[mac<<1]; struct qnode { int id; ll d; bool operator<(const qnode &a) const{ return d>a.d; } }; ll dp[mac],dis[mac]; bool vis[mac],pot[mac][mac],distry[mac]; int head[mac],num=0; void add(int u,int v,int w) { eg[++num]=node{v,head[u],w}; head[u]=num; } void dij(int n,int m) { memset(vis,false,sizeof vis); for (int i=1; i<=m; i++) dis[i]=inf; dis[1]=0; priority_queue<qnode>q; q.push(qnode{1,0}); while (!q.empty()){ qnode now=q.top(); q.pop(); int id=now.id,d=now.d; if (vis[id]) continue; vis[id]=true; for (int i=head[id]; i!=-1; i=eg[i].next){ int v=eg[i].to; if (!distry[v] && dis[id]+eg[i].w<dis[v]){ dis[v]=dis[id]+eg[i].w; q.push(qnode{v,dis[v]}); } } } } void in(int &x) { int f=0; char ch=getchar(); while (ch>'9' || ch<'0') ch=getchar(); while (ch>='0' && ch<='9') f=(f<<1)+(f<<3)+ch-'0',ch=getchar(); x=f; } int main() { //freopen("in.txt","r",stdin); int n,m,k,e; memset(head,-1,sizeof head); in(n);in(m);in(k);in(e); for (int i=1; i<=e; i++){ int u,v,w; in(u);in(v);in(w); add(u,v,w);add(v,u,w); } int d; in(d); memset(pot,false,sizeof pot); memset(distry,false,sizeof distry); for (int i=1; i<=d; i++){ int p,l,r; in(p);in(l);in(r); for (int j=l; j<=r; j++) pot[p][j]=true; } for (int i=0; i<=n; i++) dp[i]=inf; dp[0]=-k; for (int i=1; i<=n; i++){ memset(distry,false,sizeof distry); for (int j=i; j>=1; j--){ for (int k=1; k<=m; k++) if (pot[k][j]) distry[k]=true; dij(n,m); if (dis[m]==inf) break; dp[i]=min(dp[i],dp[j-1]+(i-j+1)*dis[m]+k); } } printf ("%lld ",dp[n]); return 0; }