https://codeforces.ml/contest/1422/problem/D
题目意思的大致可以描述为，在一个n*n的方格之内，给你一个起始点和一个终点，以及m个传送点。当此时的坐标与某一个传送点的x坐标或者是y坐标相同的时候，就能直接飞到传送点。问从起始点到终点的最短路径为多长。
裸最短路的题目，即我们建个图，然后跑一下dijstra就行了。但是这题不能完全按照题目给出的点来建图，m的最大取值为1e5，中间点互相建边铁定MLE，所以最后我们需要来优化一下建图。
能想到的是，其实中途的很多点之间并不需要建边。因为这道题的建图比较特殊，每两个传送点的距离和他们x或者是y的差值的绝对值有关，同一水平上的三个点，最左边的点到中间的点的距离+中间的点到最右边的点的距离是等于最左边的点到最右边的点的距离的。而当我们将这些点按照x轴以及y轴进行排序的时候，也就成了两条线上的点。而针对这样的点我们只需要将他们连接起来即可， 不需要两个点两两都需要建边。于是就少了很多的边，也就不会MLE了。这个想法在最后的代码中的体现就是讲所有的点按照x轴和y轴进行排序，然后依次相连接。再将出发点和所有的传送点以及终点和所有的传送点进行相连接即可。
在做这道题目的时候还遇到一个问题，就是第65个数据点。当时第一次交的代码是用int，最大值取的是0x3f3f3f3f，但是最大值答案是有可能比这个最大值大的。当时取这个最大值，是因为在中途中使用了dijstra，有加法的存在，害怕会出现加法的溢出，但是最后的所有数据没有这种数据出现。给出的代码是乖乖地开了ll。
#include <bits/stdc++.h> #define int long long #define INF 0x3f3f3f3f3f3f using namespace std; const int maxn = 1e6 + 7; struct edge{ int u, v, f, nxt; }; struct node{ int xx, yy, p; }; node np[maxn << 1]; edge e[maxn << 1]; int head[maxn << 1], hcnt = 0; int sx, sy, fx, fy; int x[maxn], y[maxn], n, m; int dis[maxn], T; bool vis[maxn]; void init(){ memset(head, -1, sizeof (head)); hcnt = 0; } void adde(int u, int v, int f){ e[hcnt].u = u; e[hcnt].v = v; e[hcnt].f = f; e[hcnt].nxt = head[u]; head[u] = hcnt ++; e[hcnt].u = v; e[hcnt].v = u; e[hcnt].f = f; e[hcnt].nxt = head[v]; head[v] = hcnt ++; } void dijstra(){ memset(dis, INF, sizeof (dis)); memset(vis, false, sizeof (vis)); priority_queue <pair<int, int> > q; dis[0] = 0; q.push(make_pair(0, 0)); while (!q.empty()){ int h = q.top().second; q.pop(); if (vis[h]) continue; if (h == m + 1) break; vis[h] = true; for (int i=head[h]; ~i; i=e[i].nxt){ int _v = e[i].v, d = e[i].f; if (dis[h] + d < dis[_v]){ dis[_v] = dis[h] + d; q.push(make_pair(-dis[_v], _v)); } } } } bool cmpx(const node& a, const node& b){ return a.xx < b.xx; } bool cmpy(const node& a, const node& b){ return a.yy < b.yy; } signed main(){ init(); scanf("%lld%lld", &n, &m); scanf("%lld%lld%lld%lld", &sx, &sy, &fx, &fy); for (int i=1; i<=m; i++) { scanf("%lld%lld", &x[i], &y[i]); np[i].xx = x[i]; np[i].yy = y[i]; np[i].p = i; } for (int i=1; i<=m; i++) adde(0, i, min(abs(y[i] - sy), abs(x[i] - sx))); for (int i=1; i<=m; i++) adde(i, m+1, abs(y[i] - fy) + abs(x[i] - fx)); adde(0, m+1, abs(sy - fy) + abs(sx - fx)); sort(np+1, np+1+m, cmpx); for (int i=1; i<m; i++) adde(np[i].p, np[i+1].p, np[i+1].xx - np[i].xx); sort(np+1, np+1+m, cmpy); for (int i=1; i<m; i++) adde(np[i].p, np[i+1].p, np[i+1].yy - np[i].yy); dijstra(); printf("%lld\n", dis[m + 1]); return 0; }
D. Returning Home (codeforces#675 Div. 2)
原文：https://www.cnblogs.com/MrIsland/p/13773910.html