Rockdu's Blog

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

  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

32

说明

【样例输入说明】

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

【样例输出说明】

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

_NOI导刊2010提高（01）

注意到我们每一天要变更路线一定还是走最短路。所以l~r天不变更路线的最优方案就是把l~r天所有不能走的点都删掉再求最短路。这样我们就可以进行动态规划了，设dp[i]表示第i天的最优花销。那么我们枚举在哪里切换路线更优，则有状态转移方程：dp[i] = min(dp[j] + SPFA{j ~ i天有效点集} * (i - j) + k) (j = 1...i - 1)

这里要提到一个小技巧，对于取并集的操作，bitset处理的很到位。建议每一天不可用的点用bitset存储，不仅可以精简代码还可以优化时间，下面是代码：

#include<cstdio>
#include<cstring>
#include<queue>
#include<bitset>
using namespace std;
const int maxn = 25;
const int maxd = 105;
const int inf = 0x3f3f3f3f;
 
struct edge {
    int v, w, next;
}e[maxn * maxn * 2];
 
int dis[maxn], dp[maxd], k, n, day, m, t;
int head[maxn], cnt, vis[maxn];
bitset<maxn> dels[maxd];
 
void adde(const int &u, const int &v, const int &w) {
    e[++cnt] = (edge) {v, w, head[u]};
    head[u] = cnt;
}
 
int SPFA(int L, int R) {
    bitset<maxn> del;
    for(register int i = L; i <= R; ++i) 
        del = del | dels[i];
    memset(dis, 0x3f, sizeof(dis));
    queue<int > q;
    q.push(1), vis[1] = 1, dis[1] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop(), vis[u] = 0;
        for(register int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if(del[v]) continue;
            if(dis[u] + e[i].w < dis[v]) {
                dis[v] = dis[u] + e[i].w;
                if(vis[v]) continue;
                q.push(v), vis[v] = 1;
            }
        }
    }
    return dis[n];
}
 
int main() {
    scanf("%d%d%d%d", &day, &n, &k, &m);
    int u, v, w;
    for(register int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        adde(u, v, w), adde(v, u, w);
    }
    scanf("%d", &t);
    for(register int i = 1; i <= t; ++i) {
        scanf("%d%d%d", &w, &u, &v);
        for(register int j = u; j <= v; ++j)
            dels[j][w] = 1;
    }
    dp[1] = SPFA(1, 1);
    for(register int i = 2; i <= day; ++i) {
        int ans = SPFA(1, i);
        if(ans != inf) dp[i] = ans * i;
        else dp[i] = inf;
        for(register int j = 1; j < i; ++j) {
            ans = SPFA(j + 1, i);
            if(ans != inf)
                dp[i] = min(dp[i], dp[j] + ans * (i - j) + k);
        }
    }
    printf("%d", dp[day]);
    return 0;
}