CodeForces - 1422D
二维平面给一个起点和一个终点，给m个传送门，开始位于起点，每次可以走上下左右四个方向，花费为1，当位于和给的传送门有相同的x或者y，可以直接传送到传送门，花费为0，问起点到终点的最短花费。
答案一定是起点直接走到终点，或者起点走到传送门，再从传送门走到终点。对于任意不是传送门的两个点，距离为abs(x1-x2)+abs(y1-y2)，但是有了传送门，可以先到传送门，再从传送门到目标点，可能距离会小。而任意点到传送门的距离为min(abs(x1-x2),abs(y1-y2))，也可知传送门之间的距离为min(abs(x1-x2),abs(y1-y2))。如果把每个传送门的x轴和y轴分开看，把传送门存起来对x轴和y轴分别排序，对x轴来讲，关键字x轴优先，然后排y轴，从上到下，从左到右排，两个传送门之间的距离看成x轴的距离，可以直接建m-1条双向边将m个传送门联系起来，对于y轴来讲也一样处理，这样就避免了m²建边，且对于x轴或者y周来讲这样是具有连续性的，A到B，B到C，那么A到C的一条最短路径是A->B->C，最后再将起点到每个传送门建立一条单向边，每个传送门到终点建立一条单向边，记得加上一条起点直接到终点的边。建完图后跑一遍最短路就行了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' #define INF 0x3f3f3f3f #define PI acos(-1) const int maxn=1e5+5; struct point {ll x,y,idx;}; struct edge {ll to,cost;}; typedef pair<ll, ll> p; ll n,m; vector<edge> G[maxn]; vector<point> a; point s,e; ll d[maxn]; int cmp1(point x,point y) { if(x.x!=y.x) return x.x<y.x; else return x.y<y.y; } int cmp2(point x,point y) { if(x.y!=y.y) return x.y<y.y; else return x.x<y.x; } void dijkstra(int s) { priority_queue<p,vector<p>,greater<p> >que; for(int i=1;i<=m+2;i++) d[i]=1e18; d[s]=0; que.push(p(0,s)); while(!que.empty()) { p q=que.top();que.pop(); int v=q.second; if(d[v]<q.first) continue; for(int i=0;i<G[v].size();i++) { edge e=G[v][i]; if(d[e.to]>d[v]+e.cost) { d[e.to]=d[v]+e.cost; que.push(p(d[e.to],e.to)); } } } } int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin>>n>>m; cin>>s.x>>s.y>>e.x>>e.y; s.idx=1; e.idx=2; point temp; for(int i=0;i<m;i++) { cin>>temp.x>>temp.y; temp.idx=i+3; a.push_back(temp); } G[1].push_back({2,abs(e.x-s.x)+abs(e.y-s.y)}); sort(a.begin(),a.end(),cmp1); for(int i=0;i<(int)a.size()-1;i++) { edge k; k.to=a[i+1].idx; k.cost=abs(a[i].x-a[i+1].x); G[a[i].idx].push_back(k); k.to=a[i].idx; G[a[i+1].idx].push_back(k); } sort(a.begin(),a.end(),cmp2); for(int i=0;i<(int)a.size()-1;i++) { edge k; k.to=a[i+1].idx; k.cost=abs(a[i].y-a[i+1].y); G[a[i].idx].push_back(k); k.to=a[i].idx; G[a[i+1].idx].push_back(k); } for(int i=0;i<a.size();i++) { edge k; k.to=a[i].idx; if(a[i].x==s.x||a[i].y==s.y) k.cost=0; else k.cost=min(abs(a[i].x-s.x),abs(a[i].y-s.y)); G[1].push_back(k); k.to=2; k.cost=abs(a[i].x-e.x)+abs(a[i].y-e.y); G[a[i].idx].push_back(k); } dijkstra(1); cout<<d[2]<<endl; return 0; }