题目链接：
贪心+最短路吧，如果两点之间存在一个拐点，那么经过挂点一定不会比直接到达差，这个很容易想象，因此，我们应将横纵坐标分别排序，将相邻的横纵坐标之间建边。
细节也不多，本题的关键就是如何巧妙地建边，而不是建n^2条边。哦，据说题目卡了SPFA，和我又有啥关系呢。。。
#include#include #include #include using namespace std;inline int get_num() { int num = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar(); return num;}const int maxn = 2e5 + 5, inf = 0x3f3f3f3f;int head[maxn], eid;struct Edge { int v, w, next;} edge[4 * maxn];inline void insert(int u, int v, int w) { edge[++eid].v = v; edge[eid].w = w; edge[eid].next = head[u]; head[u] = eid;}inline void insert2(int u, int v, int w) { insert(u, v, w); insert(v, u, w);}int dist[maxn], vis[maxn];struct node { int id, dist; node(int i, int d) : id(i), dist(d) {} bool operator < (const node& rhs) const { return dist > rhs.dist; }};priority_queue q;inline void dijkstra() { memset(dist, inf, sizeof(dist)); dist[1] = 0; q.push(node(1, 0)); while (!q.empty()) { int u = q.top().id; q.pop(); if (vis[u]) continue; vis[u] = 1; for (int p = head[u]; p; p = edge[p].next) { int v = edge[p].v, w = edge[p].w; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; q.push(node(v, dist[v])); } } }}struct Point { int id, x, y;} point[maxn];bool comp1(const Point& lhs, const Point& rhs) { return lhs.x < rhs.x;}bool comp2(const Point& lhs, const Point& rhs) { return lhs.y < rhs.y;}int main() { int n = get_num(); for (int i = 1; i <= n; ++i) point[i].id = i, point[i].x = get_num(), point[i].y = get_num(); sort(point + 1, point + n + 1, comp1); for (int i = 2; i <= n; ++i) insert2(point[i - 1].id, point[i].id, point[i].x - point[i - 1].x); sort(point + 1, point + n + 1, comp2); for (int i = 1; i <= n; ++i) insert2(point[i - 1].id, point[i].id, point[i].y - point[i - 1].y); dijkstra(); printf("%d", dist[n]); return 0;}