题意：
物流公司要把一批货物从码头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天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一
Output
包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。
#include<bits/stdc++.h> using namespace std; const int maxn=505; const int inf=1e9; int N,M,K,E,D; int bb[maxn][maxn]; int bad[maxn]; int dp[maxn]; struct e { int u; int v; int w; int next; }edge[maxn]; int head[maxn]; int tol; void addedge (int u,int v,int w) { edge[++tol].u=u; edge[tol].v=v; edge[tol].w=w; edge[tol].next=head[u]; head[u]=tol; } int d[maxn]; int visit[maxn]; struct node { int v; int w; }; bool operator < (node a,node b) { return a.w>b.w; } int dijkstra () { priority_queue<node> q; for (int i=1;i<=M;i++) d[i]=inf; memset(visit,0,sizeof(visit)); d[1]=0; q.push({1,d[1]}); while (!q.empty()) { int u=q.top().v; q.pop(); if (visit[u]||bad[u]) continue; visit[u]=1; for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if (!visit[v]&&!bad[v]) { if (d[v]>d[u]+edge[i].w) { d[v]=d[u]+edge[i].w; q.push({v,d[v]}); } } } } return d[M]; } int main () { scanf("%d%d%d%d",&N,&M,&K,&E); memset(head,-1,sizeof(head)); for (int i=1;i<=E;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } scanf("%d",&D); for (int i=1;i<=D;i++) { int k,x,y; scanf("%d%d%d",&k,&x,&y); for (int j=x;j<=y;j++) bb[k][j]=1; } for (int i=1;i<=N;i++) dp[i]=inf; dp[0]=0; for (int i=1;i<=N;i++) { memset(bad,0,sizeof(bad)); for (int j=i;j;j--) { for (int k=1;k<=M;k++) bad[k]+=bb[k][j]; int dd=dijkstra(); if (dd>=inf) break; dp[i]=min(dp[i],dp[j-1]+(i-j+1)*dd+K); } } printf("%d",dp[N]-K); return 0; }