[ZJOI2006]物流运输

思路

首先想如果重新规划一条路线我的花费将会是:

$cost_{1, n} = cost_{1, i - 1} + cost_{i, n} + k$
也就是在第k天我们重新找一条路去走。
我们可以发现我们的花费与这条路可走的时间是有关系的，
于是我们可以处理出 $cost[i][j] =$ 第i天到第j天这条路径均可行的最小花费，

接下来我们只要按照开头说的公式去进行 $dp$ 即可。

$dp[i]$ 表示前 $i$ 天的最小花费，所以有 $dp[i] = min(dp[i], dp[j - 1] +k + cost[j][i] * (i - j + 1))$ 。

代码

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m, maze[25][25], t[25][110], dis[25][25];

ll cost[110][110], dp[110];

int floyd(int l, int r) {
    memset(dis, 0x3f, sizeof dis);
    for(int i = 1; i <= m; i++) {
        dis[i][i] = 0;
        for(int j = 1; j < i; j++) {
            if((t[i][r] - t[i][l - 1]) || (t[j][r] - t[j][l - 1])) continue;
            dis[i][j] = dis[j][i] = maze[i][j];
        }
    }
    for(int k = 1; k <= m; k++) {
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= m; j++) {
                dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
            }
        }
    }
    return dis[1][m];
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int k, e, d;
    scanf("%d %d %d %d", &n, &m, &k, &e);
    memset(maze, 0x3f, sizeof maze);
    for(int i = 1; i <= m; i++) {
        maze[i][i] = 0;
    }
    for(int i = 1; i <= e; i++) {
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        maze[x][y] = min(maze[x][y], w);
        maze[y][x] = min(maze[y][x], w);
    }
    scanf("%d", &d);
    for(int i = 1; i <= d; i++) {
        int p, l, r;
        scanf("%d %d %d", &p, &l, &r);
        for(int j = l; j <= r; j++) {
            t[p][j] = 1;
        }
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            t[i][j] += t[i][j - 1];
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            cost[j][i] = floyd(j, i);
        }
    }
    for(int i = 1; i <= n; i++) {
        dp[i] = cost[1][i] * i;
        for(int j = 1; j <= i; j++) {
            dp[i] = min(dp[i], dp[j - 1] + k + (i - j + 1) * cost[j][i]);
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}