$回家路线$回家路线

$最初想法$最初想法

设 $Dis[i,j]$Dis[i,j] 表示使用编号为 $j$j 的边走到 $i$i 节点的最小花费, 则

$Dis[to,j]=\min \left\{Dis\right[ft,i]+A\ast (p_j-q_i{)}^2+B\ast (p_j-q_i)+C\}$Dis[to,j]=min{Dis[ft,i]+A∗(pj​−qi​)2+B∗(pj​−qi​)+C}

使用类似 $Spfa$Spfa 的方法转移, 鉴于空间复杂度为 $O\left(NM\right)$O(NM) 的, 只有 $70pts$70pts.

代码 .

$正解部分$正解部分

时间的范围很小, 考虑以枚举时刻进行 $dp$dp,

设 $F[i,j]$F[i,j] 表示时刻 $j$j 走过 $i$i 边的最小花费, 时间复杂度 $O\left(MT\right)$O(MT), ( $T$T 为最大时间) 能过 .
理论上不能 $AC$AC, 所以要优化 .

$怎么优化?$怎么优化?
每个边 出发/到达时刻 都是确定的, 于是可以建一个 时间队列,
预先在对应时刻插入边, 枚举时间时, 到了对应时刻, 再将边取出参加转移.
省掉第二维.

则设 $F\left[i\right]$F[i] 表示 走完编号为 $i$i 的边的最小花费, 则
$F\left[j\right]=\min \left\{F\right[i]+A\ast (p_j-q_i{)}^2+B\ast (p_j-q_i)+C\}$F[j]=min{F[i]+A∗(pj​−qi​)2+B∗(pj​−qi​)+C}

去掉 $\min$min 化简, 仅关于决策的项放在一左边, 剩下的放在右边,
$F\left[i\right]+A{q}_i^2-B{q}_i=2A{p}_j{q}_i-F\left[j\right]-A{p}_j^2-B{p}_j-C$F[i]+Aqi2​−Bqi​=2Apj​qi​−F[j]−Apj2​−Bpj​−C

为 $y=kx+b$y=kx+b 的形式,

• $y=F\left[i\right]+A{q}_i^2-B{q}_i$y=F[i]+Aqi2​−Bqi​
• $k=2A{p}_j$k=2Apj​
• $x=q_i$x=qi​
• $b=-F\left[j\right]-A{p}_j^2-B{p}_j-C$b=−F[j]−Apj2​−Bpj​−C

1. 因为求的是最小值, 所以维护 下凸壳;
2. 因为 $k$k 单调递增, 所以可以弹出队首 .

斜率优化 得到 $O\left(M\right)$O(M) 时间复杂度.

没学过斜率优化的可以点击 这里 .

$实现部分$实现部分

• 对每个点建单调队列, 所有到达该点的边都可以作为 从这条边出发的边 转移的来源,
  每条边更新后都需要加入其终点对应时刻的 候选单调队列 , 在对应时刻取出加入正式队列, 以便后面的边进行更新.

• 注意开始时, $1$1 节点的单调队列需要推入 $0$0 元素, 使得 $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;
}