1. 朴素 DP

将每个航班看作一个状态。设 $dp[i]$ 表示以第 $i$ 个航班作为最后一个乘坐的航班，到达其终点城市 $v_i$ 时所积累的最小总挫败感（包括在该航班到达后等待到下一航班之前的所有挫败感，但注意最后到达 $n$ 时不再需要等待，所以终点可以直接统计答案）。

初始条件：城市 $1$ 在时刻 $0$ 可以看作一个“虚拟航班”，其到达时间为 $0$，终点为城市 $1$，且挫败感为 $0$。

对于航班 $i$，如果我们之前乘坐的航班是 $j$，且满足 $v_j = u_i$ 且 $e_j \le s_i$，则转移为：

$$dp[i] = \min_{j: v_j = u_i,\ e_j \le s_i} \big( dp[j] + (s_i - e_j)^2 \big)$$

最终答案：所有终点为 $n$ 的航班 $i$ 的 $dp[i]$ 的最小值（因为到达 $n$ 后即可停止，无需再等待）。

直接枚举 $j$ 是 $O(m^2)$，不可行。

2. 斜率优化（凸包）

观察转移式：

$$dp[i] = \min_{j} \left( dp[j] + s_i^2 - 2s_i e_j + e_j^2 \right)$$

整理为关于 $x = s_i$ 的一次函数形式：

$$dp[i] = s_i^2 + \min_{j} \left( (-2e_j) \cdot s_i + (dp[j] + e_j^2) \right)$$

令直线的斜率为 $a_j = -2e_j$，截距为 $b_j = dp[j] + e_j^2$，则查询时在凸包上求 $x = s_i$ 处的最小值，加上 $s_i^2$ 即可。
由于 $e_j$ 随 $j$ 递增（按到达时间排序），斜率 $a_j = -2e_j$ 是单调递减的（因为 $e_j$ 递增，$-2e_j$ 递减）。同时查询的 $x = s_i$ 也是递增的（按起飞时间排序），因此可以使用单调队列维护凸包，查询时指针单调移动，总复杂度 $O(m)$。
但注意：并不是所有航班 $j$ 都能立即用于转移，因为必须满足 $e_j \le s_i$。因此我们需要按时间顺序动态添加直线：将航班按到达时间 $e$ 排序，处理起飞时间 $s$ 升序的航班时，将所有到达时间不超过当前 $s$ 的航班对应的直线加入其终点城市 $v_j$ 的凸包中。
于是算法流程：

• 将航班按起飞时间升序排序（用于 DP 顺序）。
• 将航班按到达时间升序排序（用于加入凸包的顺序）。
• 维护一个指针 $p$，指向按到达时间排序的数组，当处理起飞时间 $s$ 时，将所有 $e \le s$ 的航班加入其终点城市的凸包。
• 对每个航班 $i$，在其起点城市 $u_i$ 的凸包上查询 $x = s_i$ 得到最小值，计算 $dp[i]$。
• 如果 $v_i = n$，更新答案。

3. 凸包实现细节

• 每个城市单独维护一个下凸包（因为要求最小值，且斜率单调递减）。
• 直线结构体 Line { long long a, b; }。
• 添加直线时，若新直线使队尾直线变得无用，则弹出（使用叉积判断，避免浮点数）。
• 查询时，由于斜率单调递减，查询的 $x$ 单调递增，因此指针在凸包上单调移动，复杂度均摊 $O(1)$。
  注意：初始时，城市 $1$ 在时刻 $0$ 有一条直线：斜率为 $0$（因为 $e=0$），截距为 $0$（$dp=0$），表示从城市 $1$ 出发无需等待。

4. 时间复杂度

• 排序 $O(m \log m)$。
• DP 遍历每个航班 $O(m)$，每个航班加入一次凸包，查询一次凸包，总均摊 $O(m)$。
• 总复杂度 $O(m \log m)$，可通过。

易错点

• 凸包维护时需注意斜率单调性及查询指针的正确性。
• 由于存在自环（$u_i = v_i$）或起点等于终点的情况，转移时需正确处理。
• 初始直线应加入城市 $1$ 的凸包。
• 答案可能很大，使用 long long，上限设为 (1LL<<62)。

---

OK直接放代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200000+500;
const int MAXM=200000+500;
int n,m;
struct Flight{int u,v,s,e;}f[MAXM];
int ordS[MAXM],ordA[MAXM];
long long dp[MAXM];
struct Line{long long a,b;};
vector<Line> hull[MAXN];
bool bad(const Line&l1,const Line&l2,const Line&l3){
    __int128 left=(__int128)(l2.b-l1.b)*(l2.a-l3.a);
    __int128 right=(__int128)(l3.b-l2.b)*(l1.a-l2.a);
    return left>=right;
}
void add(int city,long long a,long long b){
    Line nl={a,b};
    auto &h=hull[city];
    while(h.size()>=2&&bad(h[h.size()-2],h[h.size()-1],nl))h.pop_back();
    h.push_back(nl);
}
long long query(int city,long long x){
    auto &h=hull[city];
    int l=0,r=h.size()-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(h[mid].a*x+h[mid].b <= h[mid+1].a*x+h[mid+1].b) r=mid;
        else l=mid+1;
    }
    return h[l].a*x+h[l].b;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){cin>>f[i].u>>f[i].v>>f[i].s>>f[i].e;ordS[i]=ordA[i]=i;}
    sort(ordS+1,ordS+m+1,[](int i,int j){return f[i].s<f[j].s;});
    sort(ordA+1,ordA+m+1,[](int i,int j){return f[i].e<f[j].e;});
    hull[1].push_back({0,0});
    const long long INF=(1LL<<62);
    for(int i=1;i<=m;i++)dp[i]=INF;
    long long ans=INF;
    int pa=1;
    for(int i=1;i<=m;i++){
        int id=ordS[i];
        int s=f[id].s;
        while(pa<=m&&f[ordA[pa]].e<=s){
            int j=ordA[pa];
            if(dp[j]!=INF){
                int city=f[j].v;
                long long a=-2LL*f[j].e;
                long long b=dp[j]+1LL*f[j].e*f[j].e;
                add(city,a,b);
            }
            pa++;
        }
        if(!hull[f[id].u].empty()){
            long long best=query(f[id].u,s);
            dp[id]=1LL*s*s+best;
            if(f[id].v==n)ans=min(ans,dp[id]);
        }
    }
    cout<<ans<<"\n";
    return 0;
}