# BZOJ 1003 - 物流运输

2020-03-15 02:19 CST

## Problem

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

## 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>