题目地址：洛谷：【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;
}