[ZJOI2006]物流运输 题解
题目地址:洛谷:【P1772】[ZJOI2006]物流运输 – 洛谷、BZOJ:Problem 1003. — [ZJOI2006]物流运输
题目描述
物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个n天的运输计划,使得总成本尽可能地小。
输入输出格式
输入格式:
物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个n天的运输计划,使得总成本尽可能地小。
输出格式:
包括了一个整数表示最小的总成本。总成本=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
题解
n和m非常小,尤其是m,所以可以乱搞。我们考虑预处理出一个数组dist[i][j]表示时间段[i, j]内不修改路线的最短路,这个预处理可以[eq]O(n^2)[/eq]枚举时间段每次判断该时间段内哪些点始终可用,并且跑一遍SPFA。后面就是DP,每次的决策是在何处改线路,dp[i]表示时间段[1, i]最小开销,枚举一个j<i,表示在j时间处改变路线,转移如下
\displaystyle dp[i] = \min\{dist[1][i], \min\{dp[j]+k+dist[j+1][i] \cdot (i-j)\}\}
答案即为dp[n]。
代码
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <queue>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF
: *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 105;
struct Edge {
int to, w;
};
std::vector<Edge> gra[MAXN];
int n, m, k, e, d;
int dis[MAXN];
bool del[MAXN][MAXN], ndel[MAXN], inque[MAXN];
std::queue<int> que;
inline int spfa(int s, int t) {
memset(dis, 0x3f, sizeof(dis));
memset(ndel, 0, sizeof(ndel));
for(int i = 1; i <= m; i++) {
for(int j = s; j <= t; j++) {
if(del[i][j]) {
ndel[i] = true; break;
}
}
}
dis[1] = 0; inque[1] = true; que.push(1);
while(!que.empty()) {
int u = que.front(); que.pop(); inque[u] = false;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i].to;
if(ndel[v]) continue;
if(dis[v] > dis[u] + gra[u][i].w) {
dis[v] = dis[u] + gra[u][i].w;
if(!inque[v]) {
inque[v] = true; que.push(v);
}
}
}
}
return dis[m];
}
int dist[MAXN][MAXN];
LL dp[MAXN];
int main() {
n = readint(); m = readint(); k = readint(); e = readint();
for(int i = 1, u, v, w; i <= e; i++) {
u = readint(); v = readint(); w = readint();
gra[u].push_back(Edge {v, w});
gra[v].push_back(Edge {u, w});
}
d = readint();
for(int i = 1, u, a, b; i <= d; i++) {
u = readint(); a = readint(); b = readint();
for(int j = a; j <= b; j++) {
del[u][j] = true;
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dist[i][j] = spfa(i, j);
}
}
for(int i = 1; i <= n; i++) {
dp[i] = 1ll * dist[1][i] * i;
for(int j = 1; j < i; j++) {
dp[i] = std::min(dp[i], dp[j] + k + 1ll * dist[j + 1][i] * (i - j));
}
}
printf("%lld", dp[n]);
return 0;
}