[Blog] [Docs] [Code] [Slides] [About]

BZOJ 1003 - 物流运输

最短路动态规划

2020-03-15 02:19 CST

Problem

以前$i$天已经运输完毕后更换线路进行考虑:

$$ans[n] = \min(ans[i] + dis[i+1][n] * (j - i) + k)$$

最短路直接套Floyd就够了。

本来想判断码头是否可用也用前缀+后缀数组加速的,结果WA了,很佛。

Solution

import java.util.Scanner;

class Solve {
    final int INF = 0x3f3f3f3f;
    int n, m, k, e, d;
    int[] ans;
    int[][] path;
    int[][] map;
    boolean[][] closed;
    Solve(Scanner cin) {
        n = cin.nextInt();
        m = cin.nextInt();
        k = cin.nextInt();
        e = cin.nextInt();
        ans    = new int[n + 1];
        path   = new int[n + 1][n + 1];
        map    = new int[m + 1][m + 1];
        closed = new boolean[m + 1][n + 1];
        ans[0] = -k;
        for (int i = 1; i <= n; ++i) ans[i] = -1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                path[i][j] = -1;
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= m; ++j) {
                map[i][j] = INF;
            }
            map[i][i] = 0;
        }
        for (int i = 0; i < e; ++i) {
            int u = cin.nextInt();
            int v = cin.nextInt();
            int w = cin.nextInt();
            map[u][v] = map[v][u] = w;
        }
        d = cin.nextInt();
        for (int i = 0; i < d; ++i) {
            int u = cin.nextInt();
            int l = cin.nextInt();
            int r = cin.nextInt();
            for (int d = l; d <= r; ++d) closed[u][d] = true;
        }
    }
    int dp(int day) {
        if (ans[day] != -1) return ans[day];
        int ret = INF, cur;
        for (int last = 0; last <= day - 1; ++last) {
            if (floyd(last + 1, day) != INF) {
                cur = dp(last) + (day - last) * floyd(last + 1, day) + k;
                if (cur < ret) ret = cur;
            }
        }
        return ans[day] = ret;
    }
    int floyd(int l, int r) {
        if (path[l][r] != -1) return path[l][r];
        int[][] dis = new int[m + 1][m + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= m; ++j) {
                dis[i][j] = map[i][j];
            }
        }
        for (int i = 1; i <= m; ++i) {
            boolean flag = false;
            for (int d = l; d <= r; ++d) {
                if (closed[i][d]) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                for (int j = 1; j <= m; ++j) {
                    dis[i][j] = INF;
                }
            }
        }
        for (int k = 1; k <= m; ++k) {
            for (int i = 1; i <= m; ++i) {
                for (int j = 1; j <= m; ++j) {
                    if (dis[i][k] + dis[k][j] < dis[i][j]) {
                        dis[i][j] = dis[i][k] + dis[k][j];
                    }
                }
            }
        }
        return path[l][r] = dis[1][m];
    }
    public int run() { return dp(n); }
}

public class Main {
    public static void main(String []args) {
        Scanner cin = new Scanner(System.in);
        Solve solve = new Solve(cin);
        System.out.println(solve.run());
    }
}
<EOF>