题目链接：

题目大意：

物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。

思路：

先预处理出在时间a-b内的最短路。

然后进行dp

dp[i]表示前i天的最小花费

状态转移方程：dp[i] = min(dp[i], dp[j] + cost[j + 1][j] * (i - j) + k);

dp[i]初始化为cost[1][i] * i;

1 #include
     
        2 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf  3 #define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时  4 #define Min(a, b) ((a) < (b) ? (a) : (b))  5 #define Mem(a) memset(a, 0, sizeof(a))  6 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))  7 #define MID(l, r) ((l) + ((r) - (l)) / 2)  8 #define lson ((o)<<1)  9 #define rson ((o)<<1|1) 10 #define Accepted 0 11 #pragma comment(linker, "/STACK:102400000,102400000")//栈外挂 12 using namespace std; 13 inline int read() 14 { 15     int x=0,f=1;char ch=getchar(); 16     while (ch<'0'||ch>'9'){
   if (ch=='-') f=-1;ch=getchar();} 17     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 18     return x*f; 19 } 20  21 typedef long long ll; 22 const int maxn = 100 + 10; 23 const int MOD = 1000000007;//const引用更快，宏定义也更快 24 const int INF = 1e9 + 7; 25 const double eps = 1e-6; 26  27 struct edge 28 { 29     int v; 30     ll w; 31     edge(){} 32     edge(int v, ll w):v(v), w(w){} 33 }; 34 vector
      
       e; 35 vector
       
        Map[maxn]; 36 void addedge(int u, int v, ll w) 37 { 38     e.push_back(edge(v, w)); 39     Map[u].push_back(e.size() - 1); 40 } 41 struct Heapnode 42 { 43     ll d; 44     int u; 45     Heapnode(){} 46     Heapnode(ll d, int u):d(d), u(u){} 47     bool operator < (const Heapnode& a)const 48     { 49         return d > a.d; 50     } 51 }; 52  53 bool v[maxn];//标记加入队列 54 ll d[maxn];//最短路 55 bool judge[maxn][maxn];//judge[i][j]为真表示第i个码头在j时刻不可以工作 56 bool tmp[maxn];//tmp[i]表示码头i在a-b时间段内是否可以工作 57 int n, m; 58 ll dijkstra(int a, int b, int s, int t)//在时间a-时间b内 从s-t的最短路 59 { 60     for(int i = 1; i <= m; i++)//预处理 61     { 62         tmp[i] = 1; 63         for(int j = a; j <= b; j++) 64         { 65             if(judge[i][j]){tmp[i] = 0;break;} 66         } 67     } 68     priority_queue
        
         q; 69     for(int i = 1; i <= m; i++)d[i] = INF; 70     d[s] = 0; 71     memset(v, 0, sizeof(v)); 72     q.push(Heapnode(0LL, s)); 73     while(!q.empty()) 74     { 75         Heapnode now = q.top(); 76         q.pop(); 77         int u =  now.u; 78         if(v[u])continue; 79         v[u] = 1; 80         for(int i = 0; i < Map[u].size(); i++) 81         { 82             int v = e[Map[u][i]].v; 83             ll w = e[Map[u][i]].w; 84             if(!tmp[v])continue;//v不可以工作 85             if(d[v] > d[u] + w) 86             { 87                 d[v] = d[u] + w; 88                 q.push(Heapnode(d[v], v)); 89             } 90         } 91     } 92     return d[t]; 93 } 94 ll cost[maxn][maxn];//cost[a][b]表示从时间a-时间b内的最短路 95 ll dp[maxn];//dp[i]表示前i天的最小花费 96 int main() 97 { 98     int k, e; 99     scanf("%d%d%d%d", &n, &m, &k, &e);100     for(int i = 1; i <= e; i++)101     {102         int u, v;103         ll w;104         scanf("%d%d%lld", &u, &v, &w);105         addedge(u, v, w);106         addedge(v, u, w);107     }108     scanf("%d", &e);109     for(int i = 1; i <= e; i++)110     {111         int u, a, b;112         scanf("%d%d%d", &u, &a, &b);113         for(int j = a; j <= b; j++)judge[u][j] = 1;114     }115     for(int a = 1; a <= n; a++)116         for(int b = 1; b <= n; b++)117             cost[a][b] = dijkstra(a, b, 1, m);118     for(int i = 1; i <= n; i++)119     {120         dp[i] = cost[1][i] * i;121         for(int j = 1; j < i; j++)122         {123             dp[i] = min(dp[i], dp[j] + cost[j + 1][i] * (i - j) + k);124         }125     }126     cout<
         
          <