题目链接

BZOJ1003

思路要点

枚举断点跑最短路,$dp[i]$表示前$i$的最小花费。
时间复杂度 $\mathcal O(n^3log_2n)$

代码

#include <bits/stdc++.h>

using namespace std;

template <class T>
void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}

template <class T>
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}

template <class T>
void writeln(T x) {
  write(x), puts("");
}

template <class T>
void chkmax(T& x, T y) {
  x = x > y ? x : y;
}

template <class T>
void chkmin(T& x, T y) {
  x = x < y ? x : y;
}

const int N = 250;
const int M = 2500;
const int T = 1050;
const long long inf = 0x3f3f3f3f;

struct Edge {
  int to, nt, w;
} E[M << 1];

int H[N];
int dis[N], dp[N];
int n, m, k, ed, edgeCnt = 1;
bool ban[N], vis[N], ntv[N][T];

void addEdge(int u, int v, int w) {
  E[++edgeCnt] = (Edge){v, H[u], w};
  H[u] = edgeCnt;
}

struct Node {
  int u, dis;
  
  bool operator < (Node rhs) const {
    return dis > rhs.dis;
  } 
};

void dijkstra() {
  priority_queue<Node> heap;
  memset(dis, 0x3f, sizeof dis);
  memset(vis, 0, sizeof vis);
  dis[1] = 0, heap.push((Node){1, 0});
  while (!heap.empty()) {
    int u = heap.top().u; heap.pop();
    if (vis[u]) continue; vis[u] = 1;
    for (int e = H[u]; e; e = E[e].nt) {
      int v = E[e].to;
      if (!ban[v] && dis[v] > dis[u] + E[e].w) {
        dis[v] = dis[u] + E[e].w;
        heap.push((Node){v, dis[v]});
      }
    }
  }
}

int main() {
  read(n), read(m), read(k), read(ed);
  for (int i = 1; i <= ed; i++) {
    int u, v, w; read(u), read(v), read(w);
    addEdge(u, v, w), addEdge(v, u, w);
  }
  int d; read(d);
  for (int i = 1; i <= d; i++) {
    int x, y, z; read(x), read(y), read(z);
    for (int j = y; j <= z; j++) ntv[x][j] = 1;
  }
  memset(dp, 0x3f, sizeof dp);
  dp[0] = -k;
  for (int i = 1; i <= n; i++) {
    memset(ban, 0, sizeof ban);
    for (int j = i; j >= 1; j--) {
      for (int t = 1; t <= m; t++) 
        if (ntv[t][j]) ban[t] = 1;
      dijkstra();
      if (dis[m] >= inf) break;
      chkmin(dp[i], dp[j - 1] + k + dis[m] * (i - j + 1));
    }
  }
  writeln(dp[n]);
  return 0;
}
最后修改:2020 年 02 月 27 日 03 : 53 PM
如果觉得我的文章对你有用,请随意赞赏