ZJOI2066 物流运输

原题链接:https://www.luogu.org/problem/P1772

收录于 NOI 系列题解集


思路

一看数据范围,大概是可以乱搞的。

对每个区间跑一遍 Dijkstra 最短路,预处理出不改变路径的总成本。

然后 DP 就很好想了,不多写了。转移过程注意判无限大(惯用的0x3F3F3F3F)。

不改变路径时,式子中含有dp[0],可以利用这一特点,把dp[0]设为-K

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define min(a, b) ((a) > (b) ? (b) : (a))

const int MAXN = 105, MAXM = 25, MAXE = 200;
int N, M, K, E, dp[MAXN], cost[MAXN][MAXN], D;
bool block[MAXM][MAXN];

struct Edge {
  int v, w, next;
} edge[MAXE << 1];
int head[MAXM], cnt;

inline void add(int u, int v, int w) {
  edge[cnt].v = v;
  edge[cnt].w = w;
  edge[cnt].next = head[u];
  head[u] = cnt;
  ++cnt;
}

int dist[MAXM], vis[MAXM];
std::priority_queue< std::pair<int, int> > Q;

inline void dijkstra(int l, int r) {
  memset(dist, 0x3F, sizeof(dist));
  memset(vis, false, sizeof(vis));

  for (int i = 1; i <= M; ++i) {
    for (int j = l; j <= r; ++j) {
      if (block[i][j]) {
        vis[i] = true;
        break;
      }
    }
  }

  Q.push(std::make_pair(0, 1));
  dist[1] = 0;
  while (!Q.empty()) {
    int u = Q.top().second;
    Q.pop();
    vis[u] = true;
    for (int i = head[u]; ~i; i = edge[i].next) {
      int v = edge[i].v;
      if (vis[v]) continue;
      int alt = dist[u] + edge[i].w;
      if (dist[v] > alt) {
        dist[v] = alt;
        Q.push(std::make_pair(-alt, v));
      }
    }
  }
  cost[l][r] = dist[M];
}

int main() {
  memset(head, 0xFF, sizeof(head));
  memset(block, false, sizeof(block));
  memset(dp, 0x3F, sizeof(dp));

  scanf("%d%d%d%d", &N, &M, &K, &E);
  for (int i = 0; i < E; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w);
    add(v, u, w);
  }
  scanf("%d", &D);
  for (int i = 0; i < D; ++i) {
    int u, a, b;
    scanf("%d%d%d", &u, &a, &b);
    for (int i = a; i <= b; ++i) {
      block[u][i] = true;
    }
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = i; j <= N; ++j) {
      dijkstra(i, j);
    }
  }
  dp[0] = -K;
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j < i; ++j) {
      if (dp[j] == 0x3F3F3F3F || cost[j + 1][i] == 0x3F3F3F3F) continue;
      dp[i] = min(dp[i], dp[j] + (i - j) * cost[j + 1][i] + K);
    }
  }
  printf("%d\n", dp[N]);
  return 0;
}
点赞

Leave a Reply