有一张 nn 个点 mm 条边的有向图，边有两个权值 pip_i 和 qiq_i pi<qip_i < q_i，表示若 pip_i 时刻在这条边的起点，则 qiq_i 时刻能到达这条边的终点。

你需要规划一条路线，使得从起点 11 号点出发，沿着这条路线到达终点 nn 号点。

假设路线依次经过的边为 a1,a2,...,ak{a_1,a_2,...,a_k}，则需要保证 而这条路线的代价是 qak+∑i=2kf(pai−qai−1)+f(pa1)\displaystyle q_{a_k}+\sum_{i=2}^{k}f(p_{a_i}-q_{a_{i-1}})+f(p_{a_1})，其中f(x)=Ax2+Bx+Cf(x)= Ax^2 + Bx + C

你需要使得你规划的路径的代价最小，输出这个最小代价。

n≤105,m≤105n\le 10^5, m\le10^5

LOJ3156

Solution

设f[i]f[i]表示经过第ii条边后的最小代价，那么

f[i]=minyj=xi,qj≤pi{f[j]+A(pi−qj)2+B(pi−qj)+C}=minyj=xi,qj≤pi{f[j]+Aqj2−Bqj−2Apiqj}+Api2+Bpi+C \begin{aligned} f[i]&=\min_{y_j=x_i,q_j\le p_i}\{f[j]+A(p_i-q_j)^2+B(p_i-q_j)+C\}\\ &=\min_{y_j=x_i,q_j\le p_i}\{f[j]+Aq_j^2-Bq_j-2Ap_iq_j\}+Ap_i^2+Bp_i+C \end{aligned}

显然可以在每个点内部进行斜率优化，方法见此

设j<kj < k，若jj比kk优，那么有

f[j]+A(pi−qj)2+B(pi−qj)<dp[k]+A(pi−qk)2+B(pi−qk)⇒(f[j]+Aqj2−Bqj)−(f[k]+Aqk2−Bqk)qj−qk>2Api \begin{aligned} &f[j] + A(p_i - q_j)^2 + B(p_i - q_j) < dp[k] + A(p_i - q_k)^2 + B(p_i - q_k)\\\\ \Rightarrow &\frac{(f[j] + Aq_j^2 - Bq_j) - (f[k] + Aq_k^2-Bq_k)}{q_j - q_k}>2Ap_i \end{aligned}

因为推出来是<<，所以要把条件改成kk比jj优，即

(f[j]+Aqj2−Bqj)−(f[k]+Aqk2−Bqk)qj−qk<2Api \frac{(f[j] + Aq_j^2 - Bq_j) - (f[k] + Aq_k^2-Bq_k)}{q_j - q_k}<2Ap_i

根据套路，把pp和qq一起排个序，单调队列维护下凸壳即可

需要注意，在判断弹元素的时候，需要把分母乘过去，注意不等式符号的变化

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100, Maxm = 2e5 + 100;
const int inf = 0x3f3f3f3f;

int N, M, A, B, C;
struct edge
{
	int x, y, p, q;
} E[Maxm];
vector <pii> Id;

inline int cmp (pii a, pii b) { return (a.y ? E[a.x].q : E[a.x].p) < (b.y ? E[b.x].q : E[b.x].p); }

inline int sqr (int x) { return x * x; }

struct Convex
{
	struct point { int up, down; };

	deque <point> Q;

	inline void push (int up, int down)
	{
		if (Q.size() >= 2)
		{
			point now = *Q.rbegin(), pre = *(Q.rbegin() + 1);
			// 注意这里pre也是+1，而不是-1
			while (Q.size() >= 2 && (LL) (pre.up - now.up) * (now.down - down) >= (LL) (now.up - up) * (pre.down - now.down))
			{
				Q.pop_back ();
				if (Q.size() >= 2) now = *Q.rbegin(), pre = *(Q.rbegin() + 1);
			}
		}
		Q.push_back ((point){up, down});
	}

	inline int get_dp (int t)
	{
		if (Q.empty()) return inf;
		if (Q.size() >= 2)
		{
			point now = *Q.begin(), nxt = *(Q.begin() + 1);
			while (Q.size() >= 2 && nxt.up - now.up <= 2 * A * t * (nxt.down - now.down)) /**/
			{
				Q.pop_front ();
				if (Q.size() >= 2) now = *Q.begin(), nxt = *(Q.begin() + 1);
			}
		}
		return Q.front().up + A * t * t - 2 * A * t * Q.front().down + B * t + C;
	}

} P[Maxn];

int Dp[Maxm];

inline void Solve ()
{
	sort (Id.begin(), Id.end(), cmp);
	for (int i = 1; i <= M; ++i) Dp[i] = inf;
	P[1].push (0, 0);

	int ans = inf;
	for (int i = 0; i < Id.size(); ++i)
	{
		int x = Id[i].x, op = Id[i].y, t = op ? E[x].q : E[x].p;
		if (!op) Dp[x] = P[E[x].x].get_dp (t);
		else
		{
			if (Dp[x] >= inf) continue;
			if (E[x].y == N) Chkmin (ans, Dp[x] + E[x].q);
			else P[E[x].y].push (Dp[x] + A * sqr (t) - B * t, t);
		}
	}

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>(), A = read<int>(), B = read<int>(), C = read<int>();
	for (int i = 1; i <= M; ++i)
	{
		int x = read<int>(), y = read<int>(), p = read<int>(), q = read<int>();
		E[i] = (edge){x, y, p, q};
		Id.pb (mp (i, 0)), Id.pb (mp (i, 1));
	}
}

int main()
{

	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);

	Input ();
	Solve ();

	return 0;
}