[ZJOI2007] 物流运输

大意

• 给定一张无向联通图，有边权。
• 考虑若干天，每天有一些节点不可用。
• 每天一条路径，若当天的路径与前一天不同，有额外花费 $k$ 。
• 求总花费最小，即求每天的路径权综合与切换路径的花费的和最小。

题解

考虑 dp 。

设 $f(i)$ 为第 $i$ 天最小花费，包括切换路径的花费 。

考虑每天，$f(i)$ 已经计算。
枚举规划之后 $j$ 天的路径，计算在这若干天中都可以使用且不变化的最小路径长度 $d$ ，然后：

$$f(i + j) = f(i) + dj + k$$

给一条按照能用 $x$ 天计算的路径更新 $f(i + y), y \lt x$ 肯定不优，因此每次计算 $d$ 只有更新最后的即可。

先预处理节点 $u$ 在第 $i$ 天时还能连续用几天 $g(u, i)$ 即可：

$$g(u, i) = \begin{cases} g(u, i + 1) & \text{available} \\\\ 0 & \text{otherwise} \end{cases} \newline$$

代码

提交记录

/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P1772
    title: [ZJOI2006] 物流运输
date: 2022-09-12
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 30, MAXD = 110;

int day, n, cost, m;
vector<pair<int, int>> edges[MAXN];
bool available[MAXN][MAXD];
int left_time[MAXN][MAXD];
ll dp[MAXD];

void setup()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> day >> n >> cost >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back({v, w});
        edges[v].push_back({u, w});
    }

    for (int i = 1; i <= n; i++) fill(available[i] + 1, available[i] + day + 1, 1);
    int cnt;
    cin >> cnt;
    while (cnt--) {
        int u, x, y;
        cin >> u >> x >> y;
        for (int i = x; i <= y; i++) available[u][i] = false;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = day; j >= 1; j--)
            left_time[i][j] = available[i][j] ? left_time[i][j + 1] + 1 : 0;
    }

    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;
}

int dis[MAXN];
bool vis[MAXN];
ll dijkstra(int l, int r)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({dis[1], 1});

    while (q.size()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto e : edges[u]) {
            int v = e.first, w = e.second;
            if (l + left_time[v][l] - 1 < r) continue;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }

    return dis[n];
}

void solve(int d)
{
    for (int i = d; i <= day; i++) {
        ll dis = dijkstra(d, i);
        dp[i + 1] = min(dp[i + 1], dp[d] + (i - d + 1) * dis + cost);
    }
}

int main()
{
    setup();
    for (int i = 1; i <= day; i++) solve(i);
    cout << dp[day + 1] - cost << endl;
}