[Luogu P1772] [BZOJ 1003] [ZJOI2006]物流运输

洛谷传送门

BZOJ传送门

题目描述

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

输入输出格式

输入格式：

第一行是四个整数$n(l\le n\le 100)$、$m(l\le m\le 20)$、$K$和$e$。$n$表示货物运输所需天数，$m$表示码头总数，$K$表示每次修改运输路线所需成本，$e$表示航线条数。接下来$e$行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度($>0$)。其中码头$A$编号为$1$，码头$B$编号为$m$。单位长度的运输费用为$1$。航线是双向的。再接下来一行是一个整数$d$，后面的$d$行每行是三个整数$P(1<P<m)$，$a$，$b(1\le a\le b\le n)$。表示编号为$P$的码头从第$a$天到第$b$天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头$A$到码头$B$的运输路线。

输出格式：

包括了一个整数表示最小的总成本。总成本=$n$天运输路线长度之和+$K$*改变运输路线的次数。

输入输出样例

输入样例#1：

5 5 10 8 1 2 1 1 3 3 1 4 2 2 3 2 2 4 4 3 4 1 3 5 2 4 5 2 4 2 2 3 3 1 1 3 3 3 4 4 5

输出样例#1：

32

说明

【样例输入说明】

上图依次表示第$1$至第$5$天的情况，阴影表示不可用的码头。

【样例输出说明】

前三天走$1-4-5$，后两天走$1-3-5$，这样总成本为$(2+2)\ast 3+(3+2)\ast 2+10=32$。

解题分析

$m$范围如此小， 显然我们可以直接每次求出最短路大力$dp$。

我们在第$i$天显然有两个抉择： 更换成新的路径， 或从第$j$天开始就走一样的最短路。

这样我们就很好写出$dp$转移方程了： $dp[i]=mi{n}_{j=1}^i(dp[j-1]+(i-j+1)\times le{n}_{1\to m}+k)$， 初始状态为$dp[0]=-k$（因为显然多算了一次更换最短路的费用）。

代码如下：

#include <cstdio> #include <cctype> #include <cmath> #include <cstdlib> #include <cstring> #include <algorithm> #include <queue> #define R register #define IN inline #define W while #define MX 25 #define gc getchar() #define ll long long template <class T> IN void in(T &x) { x = 0; R char c = gc; for (; !isdigit(c); c = gc); for (; isdigit(c); c = gc) x = (x << 1) + (x << 3) + c - 48; } int dot, day, line, cnt, del; int head[MX], out[MX], stat[MX][105]; ll dis[MX], dp[105]; bool inq[MX]; struct Edge {int to, len, nex;} edge[MX << 4];//?? std::queue <int> q; IN void add(R int from, R int to, R int len) {edge[++cnt] = {to, len, head[from]}, head[from] = cnt;} IN ll SPFA() { std::memset(dis, 63, sizeof(dis)); dis[1] = 0; R int now, i; q.push(1); W (!q.empty()) { now = q.front(); q.pop(); for (i = head[now]; i; i = edge[i].nex) { if(out[edge[i].to] || dis[edge[i].to] <= dis[now] + edge[i].len) continue; dis[edge[i].to] = dis[now] + edge[i].len; if(!inq[edge[i].to]) q.push(edge[i].to), inq[edge[i].to] = true; } inq[now] = false; } return dis[dot]; } int main(void) { int a, b, c, buf; R int i, j, k; ll res; in(day), in(dot), in(del), in(line); std::memset(dp, 63, sizeof(dp)); dp[0] = -del; for (i = 1; i <= line; ++i) in(a), in(b), in(c), add(a, b, c), add(b, a, c); in(buf); for (i = 1; i <= buf; ++i) { in(a), in(b), in(c); for (j = b; j <= c; ++j) stat[a][j] = true; } for (i = 1; i <= day; ++i) { std::memset(out, 0, sizeof(out)); for (j = i; j; --j) { for (k = 1; k <= dot; ++k) out[k] |= stat[k][j]; res = SPFA(); if(res == dis[0]) continue; dp[i] = std::min(dp[i], dp[j - 1] + 1ll * (i - j + 1) * res + del); } } printf("%lld", dp[day]); }