代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct Vec {
  int x, y;
  
  Vec() : x(0), y(0) {}
  Vec(int x, int y) : x(x), y(y) {}
  
  Vec operator+(const Vec& rhs) const { return Vec(x + rhs.x, y + rhs.y); }
  Vec operator-() const { return Vec(-x, -y); }
  Vec operator-(const Vec& rhs) const { return *this + (-rhs); } 
  
  ll operator*(const Vec& rhs) const { return x * (ll)rhs.y - y * (ll)rhs.x; }
  ll operator^(const Vec& rhs) const { return x * (ll)rhs.x + y * (ll)rhs.y; }
};

const int N = 100010, M = 200010, K = 1010;

int n, m, A, B, C; 
int ptr[N];
int x[M], y[M], p[M], q[M], res[M];

vector<int> start[K], dest[K];
vector<Vec> hull[N];

void chkmin(int& x, int y) {
  if (x > y) x = y;
}

int main() {
  freopen("route.in", "r", stdin);
  freopen("route.out", "w", stdout);
  
  // A(t - s)^2 + B(t - s) + C = At^2 + As^2 - 2Ast + Bt - Bs + C
  // = (As^2 - Bs) * 1 + s * -2At + At^2+Bt + C
  // = (Res+As^2-Bs, s)^(1, -2At) + At^2+Bt+C
  
  scanf("%d%d%d%d%d", &n, &m, &A, &B, &C);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d%d", &x[i], &y[i], &p[i], &q[i]);
    start[p[i]].push_back(i);
    dest[q[i]].push_back(i);
  }
  memset(res, -1, sizeof(res));
  int ans = -1;
  hull[1].push_back(Vec(0, 0));
  for (int t = 0; t <= 1000; ++t) {
    for (int i : dest[t]) {
      if (res[i] == -1) continue;
      if (y[i] == n)
        if (ans == -1 || ans > res[i] + t)
          ans = res[i] + t;
      Vec ins(t, res[i] + (A * t - B) * t);
      if (hull[y[i]].empty()) {
        hull[y[i]].push_back(ins);
        continue;
      }
      if (hull[y[i]].back().x == t && hull[y[i]].back().y < ins.y)
        continue;
      int top = (int)hull[y[i]].size() - 1;
      while (top && ((hull[y[i]][top] - hull[y[i]][top - 1]) * (ins - hull[y[i]][top])) <= 0) {
        top--;
        hull[y[i]].pop_back();
      }
      hull[y[i]].push_back(ins);
    }
    for (int i : start[t]) {
      if (hull[x[i]].empty()) continue;
      Vec chk(-2 * A * t, 1);
      ptr[x[i]] = min(ptr[x[i]], (int)hull[x[i]].size() - 1);
      int& p = ptr[x[i]];
      while (p + 1 < hull[x[i]].size() && (chk ^ hull[x[i]][p + 1]) <= (chk ^ hull[x[i]][p]))
        ++p;
      res[i] = (chk ^ hull[x[i]][p]) + (A * t + B) * t + C;
    }
  } 
  printf("%d\n", ans);
  
  return 0;
}

评测结果