Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 5868
Solved 2424

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

HINT

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

Source

SPFA 最短路+动规.

DP 转移方程有这样: 记 cost[i][j] 为第 i 天到第 j 天都走同一路线的费用, 再记 f[i] 为从第一天到第 n 天的花费最小值, 然后就有转移方程:f[i] = min{f[j] + cost[j + 1][i] * (i - j) + k} for j in range[1, i - 1] or min{cost[1][i]}.

话说题目数据很坑 233, 因为 maxn 和 maxm 和 maxe 的差别看了我好长时间才用 gdb 调出结果, 发现数组开的太小太小了~ SPFA 直接SIGSEGV 啊 2333


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
const int maxn = 210, maxm = 25, maxe = 1000;
const long long infinit = 0x3f3f3f3f3f3f3f3fll;

class SPFA
{
public:
    struct edge { int u, v, len; edge* next; };
    edge        *edges[maxm], epool[maxe];
    int         ecnt, inque[maxm], n, s, t;
    long long   dist[maxm];
    queue<int>  que;
    void addedge(int u, int v, int len)
    {
        edge *p = &epool[++ecnt], *q = &epool[++ecnt];
        p->u = u; p->v = v; p->len = len; p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->len = len; q->next = edges[v]; edges[v] = q;
        return ;
    }
    void clear(void)
    {
        ecnt = 0;
        for (int i = 1; i <= n; i++)
            edges[i] = NULL, dist[i] = infinit;
        memset(epool, 0, sizeof(epool));
        memset(inque, 0, sizeof(inque));
        return ;
    }
    void process(void)
    {
        while (!que.empty()) que.pop();
        for (int i = 1; i <= n; i++) dist[i] = infinit;
        dist[s] = 0; inque[s] = true; que.push(s);
        while (!que.empty()) {
            int p = que.front(); que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next) {
                if (dist[p] >= infinit);
                if (dist[ep->v] > dist[p] + ep->len) {
                    dist[ep->v] = dist[p] + ep->len;
                    if (!inque[ep->v]) {
                        inque[ep->v] = true;
                        que.push(ep->v);
                    }
                }
            }
            inque[p] = false;
        }
        return ;
    }
    void dumpme()
    {
        for (int i = 1; i <= n; i++) {
            for (edge *ep = edges[i]; ep; ep = ep->next)
                printf("dumping %d -> %d : %d\n", ep->u, ep->v, ep->len);
        }
        return ;
    }
} graph;

int         n, m, K, e, P;
int         avail[maxm][maxn][maxn], prevail[maxm][maxn];
int         edge_data[maxe][3];
long long   cost[maxn][maxn], f[maxn];

int main(int argc, char** argv)
{
    // Read basic graph from input
    scanf("%d%d%d%d", &n, &m, &K, &e);
    for (int i = 1; i <= e; i++)
        scanf("%d%d%d", &edge_data[i][0], &edge_data[i][1], &edge_data[i][2]);
    // Reset 'available' array to 1
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            prevail[i][j] = 1;
    // Read unavailable data from input
    scanf("%d", &P);
    for (int i = 1, a, b, c; i <= P; i++) {
        scanf("%d%d%d", &a, &b, &c);
        for (int j = b; j <= c; j++)
            prevail[a][j] = 0;
    }
    // Preprocess available data
    memset(avail, 0, sizeof(avail));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            avail[i][j][j] = prevail[i][j];
            for (int k = j + 1; k <= n; k++) {
                avail[i][j][k] = avail[i][j][k - 1] && prevail[i][k];
                if (!avail[i][j][k])
                    break;
            }
        }
    // Build graph for n * n times
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {
            graph.n = m; graph.s = 1; graph.t = m;
            graph.clear();
            for (int k = 1; k <= e; k++)
                if (avail[edge_data[k][0]][i][j] && avail[edge_data[k][1]][i][j])
                    graph.addedge(edge_data[k][0], edge_data[k][1], edge_data[k][2]);
            graph.process();
            cost[i][j] = graph.dist[graph.n];
        }
    // Dynamic programming resolves the result
    for (int i = 1; i <= n; i++) {
        f[i] = cost[1][i] < infinit ? cost[1][i] * i : infinit;
        for (int j = 1; j <= i - 1; j++)
            if (f[j] < infinit && cost[j + 1][i] < infinit)
                f[i] = min(f[i], f[j] + cost[j + 1][i] * (i - j) + K);
    }
    long long res = f[n];
    printf("%lld\n", res);
    return 0;
}
# Sometimes generate impossible data, beware.
from pydatagen import *
n = randrange(1, 100)
m = randrange(3, 20)
K = randrange(10, 1000)
e = randrange(m, m * (m - 1) / 2 + 1)
printf('%d %d %d %d\n' % (n, m, K, e))
G = Graph(m, e, connected=True, weighed=True, weight_range=range(1, 10))
print_oi(G)
d = randrange(1, m * m / 4)
printf('%d\n' % d)
for i in range(0, d):
    tmp = randlist(2, range(1, n + 1), distinct=True)
    if tmp[1] < tmp[0]: tmp[0], tmp[1] = tmp[1], tmp[0]
    printf('%d %d %d\n' % (randrange(1, m + 1), tmp[0], tmp[1]))
fclose()