BZOJ 1003 物流运输

发表于 更新于 本文字数： 2.9k 阅读时长 ≈ 5 分钟

题目链接：BZOJ 1003 物流运输

Problem

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

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

Solution

Idea

我们可以看到码头数最多为 20，较少，故我们可以记录出每个天数区间内最短路，最终用 dp 来解决。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 21

typedef long long LL;

using namespace std;

int n, m, k;
int tot;
bool flag[MAXN][101];
int head[MAXN];
LL cost[101][101];

LL ans[101];

struct edg
{
    int to, next, cost;
} edge[801];


void init()
{
    tot = 0;
    for(int i=0; i<MAXN; i++)
        head[i] = -1;
}

void addedge(int u, int v, int w)
{
    edge[tot].to = v;
    edge[tot].cost = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}

int spfa(int a, int b)
{
    bool block[MAXN];
    bool inq[MAXN];
    int dis[MAXN];
    int que[500];

    memset(block, false, sizeof(block));
    memset(inq, false, sizeof(inq));
    memset(dis, 0x3f, sizeof(dis));

    for(int i=1; i<=m; i++)
        for(int j=a; j<=b; j++)
            if(flag[i][j])
            {
                block[i] = true;
                break;
            }

    dis[1] = 0;
    que[0] = 1;
    inq[1] = true;
    int bg=0, ed=1;

    int u, v, w;
    while(bg<ed)
    {
        u = que[bg];

        for(int i=head[u]; ~i; i=edge[i].next)
        {
            v = edge[i].to;
            w = edge[i].cost;

            if(!block[v] && dis[u]+w < dis[v])
            {
                dis[v] = dis[u] + w;
                if(!inq[v])
                {
                    que[ed++] = v;
                    inq[v] = true;
                }
            }
        }
        bg++;
        inq[u] = false;
    }

    return dis[m];
}

void dp()
{
    for(int i=1; i<=n; i++)
    {
        ans[i] = cost[1][i] * i;
        for(int j=0; j<i; j++)
            ans[i] = min(ans[i], ans[j]+k+cost[j+1][i]*(i-j) );
    }
}

int main()
{
    init();
    int e, d;
    scanf("%d%d%d%d", &n, &m, &k, &e);
    int u, v, w;
    for(int i=0; i<e; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }

    scanf("%d", &d);
    int l, r, id;
    for(int i=0; i<d; i++)
    {
        scanf("%d%d%d", &id, &l, &r);
        for(int j=l; j<=r; j++)
            flag[id][j] = true;
    }

    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++)
            cost[i][j] = spfa(i, j);

    dp();


    printf("%lld\n", ans[n]);
    return 0;
}

Note

这题最终感觉应该很快就能过，结果写出来一直 T。卡了很久，最终发现是数组开错了。。。把 cost[101][101] 开成了 cost[MAXN][MAXN] ，找了很久的 bug，太难受了。

mark各种玄学优化时间，没想到最终进了 fast 榜。

mark