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

题解

团长神智不清的时候盯着这题看了一节课。。结果发现自己看错题了。。

缓过神来以后感觉还是很简单的。。

首先预处理出 ci,j c_{i, j} ，意义是保证所有码头在第 i i 天到第 j j 天都可以运输货物的情况下不更换运输计划的最小运输费用，这个可以用最短路算法处理出来。

设 f(i) f(i) 为第 i i 天时的最小费用，那么有显然的转移：

f(i)=minj=1i−1(f(i),f(j)+cj+1,i+k) f(i) = \min\limits_{j = 1}^{i - 1} (f(i), f(j) + c_{j + 1, i} + k)

其中 k k 是改变一次运输计划带来的额外代价。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#include <algorithm>
const int MAX_N = 100 + 10;
const int MAX_M = 20 + 10;
const int MAX_E = MAX_M * MAX_M;
const int INF = 2e9;
struct Edge {
    int x, y, w;
    int ne;
} e[MAX_E + 10];
int v[MAX_M + 1], num;
inline void put(int x, int y, int z) {
    num++;
    e[num].x = x, e[num].y = y, e[num].w = z;
    e[num].ne = v[x], v[x] = num;
}
int n, m, k, tot;
bool del[MAX_M + 1][MAX_N + 1], invalid[MAX_M + 1];
int f[MAX_N + 1], cost[MAX_N + 1][MAX_N + 1];
int dist[MAX_M + 1];
bool inq[MAX_M + 1];
inline int spfa() {
    std::queue<int> q;
    memset(inq, 0, sizeof(inq));
//	for (int i = 1; i <= m; i++) dist[i] = INT_MAX;
    memset(dist, 0x7f, sizeof(dist));
    dist[1] = 0;
    inq[1] = true;
    while (!q.empty()) q.pop();
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        inq[x] = false;
        for (int i = v[x]; i; i = e[i].ne) {
            int y = e[i].y;
            if (!invalid[y] && dist[y] > dist[x] + e[i].w) {
                dist[y] = dist[x] + e[i].w;
                if (!inq[y]) {
                    inq[y] = true;
                    q.push(y);
                }
            }
        }
    }
    return dist[m];
}
int main() {
    scanf("%d %d %d %d", &n, &m, &k, &tot);
    for (int i = 1; i <= tot; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        put(x, y, z);
        put(y, x, z);
    }
    int d;
    scanf("%d", &d);
    for (int i = 1; i <= d; i++) {
        int p, a, b;
        scanf("%d %d %d", &p, &a, &b);
        for (int j = a; j <= b; j++) {
            del[p][j] = true;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            memset(invalid, 0, sizeof(invalid));
            for (int k = 1; k <= m; k++)
                for (int a = i; a <= j; a++)
                    invalid[k] |= del[k][a];
            cost[i][j] = spfa();
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (cost[i][j] < INF) cost[i][j] *= (j - i + 1);
        }
    }
    for (int i = 1; i <= n; i++) f[i] = cost[1][i];
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            f[i] = std::min(f[i], f[j] + cost[j + 1][i] + k);
        }
    }
    printf("%d\n", f[n]);
    return 0;
}