我感觉还......不好（确实需要想）

不建议抄

思路和第一题解差不多（在此@egogaming，感谢题解提供思路）
基本思路差别不大，但是有些改动，感觉代码上更好理解
主要是时间换空间，节省了代码量，看起来更简洁，让看的人不那么难懂了（应该？）
（主要可能是因为写了太长的没多少数学字符的解释叭......）

首先理解题目：
有N个城市，每个城市有坐标(x,y)
从城市A(ax,ay)滑到城市B(bx,by)的时间为min{|ax-bx|, |ay-by|}
要从城市1到城市N，求最短时间

不难理解，最短路嘛

难点在于：

对于这种特殊的距离定义，我们可以考虑建图的方式：
如果直接对所有点两两连边，会得到n²条边，对于n=2×10⁵会爆掉
需要优化建图

优化策略：

对于任意两个点，我们可以通过其他点中转可能获得更短路径
但距离函数min{|ax-bx|, |ay-by|}有一个特点：如果我们按照某个维度排序，相邻点在这个维度上的距离就是最优的
按x坐标排序，相邻点连边（距离为x坐标差）
按y坐标排序，相邻点连边（距离为y坐标差）
这样可以保证最短路径的存在

优化方式の代码实现（理论）：

按x坐标排序，相邻点连双向边，权重为|x_i - x_j|
按y坐标排序，相邻点连双向边，权重为|y_i - y_j|
（可以明显看出，如果要从一个点到另一个点，最短路径要么是直接按规则移动，要么可以通过中间点。而按坐标排序后相邻点连边能保证我们能找到最优路径，因为任意两点间的最短路径都可以通过一系列"按单一坐标方向移动"的步骤组成）

思路总结：

将所有城市按x坐标排序，相邻城市连双向边，边权为x坐标差的绝对值
将所有城市按y坐标排序，相邻城市连双向边，边权为y坐标差的绝对值
使用Dijkstra算法求城市1到城市n的最短路

注：

由于可能有重复坐标的点，需要特别处理这些点，它们之间距离为0

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
const int N=2e5+5;
int n;
struct point{
    int x,y,id;
};
vector<point> ve;
bool cmp_x(point a,point b){
    return a.x<b.x;
}
bool cmp_y(point a,point b){
    return a.y<b.y;
}
void dfs(){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    vector<int> dist(n,1e18);
    vector<vector<pair<int,int>>> g(n);
    for(int i=0;i<n;i++){
        ve[i].id=i;
    }
    sort(ve.begin(),ve.end(),cmp_x);
    for(int i=0;i<n-1;i++){
        int u=ve[i].id,v=ve[i+1].id;
        int w=ve[i+1].x-ve[i].x;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    sort(ve.begin(),ve.end(),cmp_y);
    for(int i=0;i<n-1;i++){
        int u=ve[i].id,v=ve[i+1].id;
        int w=ve[i+1].y-ve[i].y;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dist[0]=0;
    q.push({0,0});
    while(!q.empty()){
        auto [d,u]=q.top();
        q.pop();
        if(d>dist[u]){
            continue;
        }
        for(auto [v,w]:g[u]){
            if(dist[u]+w<dist[v]){
                dist[v]=dist[u]+w;
                q.push({dist[v],v});
            }
        }
    }
    cout<<dist[n-1]<<endl;
}
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        ve.push_back({x,y});
    }
    dfs();
}

第一次正式写题解好累啊（）（）（）