设 D i s [ i , j ] Dis[i,j] Dis[i,j] 表示使用编号为 j j j 的边走到 i i i 节点的最小花费, 则
D i s [ t o , j ] = min { D i s [ f t , i ] + A ∗ ( p j − q i ) 2 + B ∗ ( p j − q i ) + C } Dis[to, j]=\min\{Dis[ft, i] + A*(p_j-q_i)^2 + B*(p_j-q_i) + C\} Dis[to,j]=min{Dis[ft,i]+A∗(pj−qi)2+B∗(pj−qi)+C}
使用类似 S p f a Spfa Spfa 的方法转移, 鉴于空间复杂度为 O ( N M ) O(NM) O(NM) 的, 只有 70 p t s 70pts 70pts.
代码 .
时间的范围很小, 考虑以枚举时刻进行 d p dp dp,
设 F [ i , j ] F[i, j] F[i,j] 表示时刻 j j j 走过 i i i 边的最小花费, 时间复杂度 O ( M T ) O(MT) O(MT), ( T T T 为最大时间) 能过 . 理论上不能 A C AC AC, 所以要优化 .
怎 么 优 化 ? 怎么优化? 怎么优化? 每个边 出发/到达时刻 都是确定的, 于是可以建一个 时间队列, 预先在对应时刻插入边, 枚举时间时, 到了对应时刻, 再将边取出参加转移. 省掉第二维.
则设 F [ i ] F[i] F[i] 表示 走完编号为 i i i 的边的最小花费, 则 F [ j ] = min { F [ i ] + A ∗ ( p j − q i ) 2 + B ∗ ( p j − q i ) + C } F[j] = \min\{F[i]+A*(p_j-q_i)^2 + B*(p_j-q_i) + C\} F[j]=min{F[i]+A∗(pj−qi)2+B∗(pj−qi)+C}
去掉 min \min min 化简, 仅关于决策的项放在一左边, 剩下的放在右边, F [ i ] + A q i 2 − B q i = 2 A p j q i − F [ j ] − A p j 2 − B p j − C F[i]+Aq_i^2-Bq_i=2Ap_jq_i-F[j]-Ap_j^2-Bp_j-C F[i]+Aqi2−Bqi=2Apjqi−F[j]−Apj2−Bpj−C
为 y = k x + b y = kx + b y=kx+b 的形式,
y = F [ i ] + A q i 2 − B q i y=F[i]+Aq_i^2 - Bq_i y=F[i]+Aqi2−Bqi k = 2 A p j k=2Ap_j k=2Apj x = q i x=q_i x=qi b = − F [ j ] − A p j 2 − B p j − C b = -F[j]-Ap_j^2-Bp_j-C b=−F[j]−Apj2−Bpj−C 因为求的是最小值, 所以维护 下凸壳;因为 k k k 单调递增, 所以可以弹出队首 .斜率优化 得到 O ( M ) O(M) O(M) 时间复杂度.
没学过斜率优化的可以点击 这里 .
对每个点建单调队列, 所有到达该点的边都可以作为 从这条边出发的边 转移的来源, 每条边更新后都需要加入其终点对应时刻的 候选单调队列 , 在对应时刻取出加入正式队列, 以便后面的边进行更新.
注意开始时, 1 1 1 节点的单调队列需要推入 0 0 0 元素, 使得 1 1 1 出发的边得到转移 .
转移时需判断决策来源是否为空, 即判断 指定边 的 出发点 的单调队列是否为空 .
转移时对每个点建单调队列保证了空间的来源正确, 遍历时间保证了时间的来源正确 .
#include<cstdio> #include<vector> #include<queue> #define pb push_back #define reg register const int maxn = 2e5 + 10; int N; int M; int A; int B; int C; int Max_time; int F[maxn]; struct Edge{ int x, y, p, q; } E[maxn]; double X(int i){ return E[i].q; } double Y(int i){ return F[i] + A*E[i].q*E[i].q - B*E[i].q; } double slope(int x, int y){ return (Y(x) - Y(y)) / (X(x) - X(y)); } std::deque <int> Q[100005]; std::vector <int> Time_line[3005]; std::vector <int> Get_off[3005]; int main(){ scanf("%d%d%d%d%d", &N, &M, &A, &B, &C); for(reg int i = 1; i <= M; i ++){ scanf("%d%d%d%d", &E[i].x, &E[i].y, &E[i].p, &E[i].q); Max_time = std::max(Max_time, E[i].p); Time_line[E[i].p].pb(i); } int Ans = 0x7f7f7f7f; Q[1].pb(0); for(reg int tim = 0; tim <= Max_time; tim ++){ int size = Get_off[tim].size(); for(reg int j = 0; j < size; j ++){ int id = Get_off[tim][j]; int t1 = E[id].y; while(Q[t1].size() >= 2 && slope(Q[t1][Q[t1].size()-1], Q[t1][Q[t1].size()-2]) >= slope(Q[t1][Q[t1].size()-2], id)) Q[t1].pop_back(); Q[t1].push_back(id); } size = Time_line[tim].size(); for(reg int k = 0; k < size; k ++){ int j = Time_line[tim][k]; int t1 = E[j].x; if(Q[t1].size() == 0) continue ; double K = 2*A*E[j].p; while(Q[t1].size() >= 2 && slope(Q[t1][0], Q[t1][1]) < K) Q[t1].pop_front(); int i = Q[t1].front(); F[j] = F[i] + A*(E[j].p-E[i].q)*(E[j].p-E[i].q) + B*(E[j].p - E[i].q) + C; Get_off[E[j].q].pb(j); if(E[j].y == N) Ans = std::min(Ans, F[j]+E[j].q); } } printf("%d\n", Ans); return 0; }