所以問題轉(zhuǎn)換為了如何在傳送門之間建圖，不難發(fā)現(xiàn)如果 x 坐標相同或者 y 坐標相同的傳送門都是可以無花費且相互可達的，而 x 軸或 y 軸不同的傳送門，其之間的距離實質(zhì)上就是兩條坐標軸之間的距離，至多有 m 條 x 軸和 m 條 y 軸需要處理，離散化一下建圖就好了
也不知道計算過程中會不會爆 int ，就直接開了 long long
代碼： ?
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;//頂點數(shù) const int M=1e6+100;//邊數(shù) vector<pair<int,int>>node;vector<int>X,Y;template<typename T>
struct Dij
{const static int N=1e6+100;const static int M=1e6+100;struct Edge{int to,next;T w;}edge[M];int head[N],cnt;//鏈式前向星 T d[N];bool vis[N];void addedge(int u,int v,T w){edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].to=u;edge[cnt].w=w;edge[cnt].next=head[v];head[v]=cnt++;}struct Node{int to;T w;Node(int TO,T W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;}};void Dijkstra(int st){priority_queue<Node>q;memset(vis,false,sizeof(vis));memset(d,0x3f,sizeof(d));d[st]=0;q.push(Node(st,0));while(q.size()){Node cur=q.top();int u=cur.to;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i!=-1;i=edge[i].next)//掃描出所有邊 {int v=edge[i].to;T w=edge[i].w;if(d[v]>d[u]+w)//更新 {d[v]=d[u]+w;q.push(Node(v,d[v]));}}}}void init(){memset(head,-1,sizeof(head));cnt=0; }
};Dij<LL>t;int get_id_x(int x)
{return lower_bound(X.begin(),X.end(),x)-X.begin()+node.size();
}int get_id_y(int y)
{return lower_bound(Y.begin(),Y.end(),y)-Y.begin()+node.size()+X.size();
}void discreate()
{sort(X.begin(),X.end());sort(Y.begin(),Y.end());X.erase(unique(X.begin(),X.end()),X.end());Y.erase(unique(Y.begin(),Y.end()),Y.end());for(int i=1;i<X.size();i++)t.addedge(i+node.size()-1,i+node.size(),X[i]-X[i-1]);for(int i=1;i<Y.size();i++)t.addedge(i+node.size()+X.size()-1,i+node.size()+X.size(),Y[i]-Y[i-1]);
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);t.init();int n,m;scanf("%d%d",&n,&m);int sx,sy,fx,fy;scanf("%d%d%d%d",&sx,&sy,&fx,&fy);node.emplace_back(sx,sy);node.emplace_back(fx,fy);X.push_back(sx);Y.push_back(sy);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);X.push_back(x);Y.push_back(y);node.emplace_back(x,y);}discreate();for(int i=0;i<node.size();i++){if(i==1)//如果是終點的話就不需要與傳送門連邊了continue;int x,y;tie(x,y)=node[i];t.addedge(get_id_x(x),i,0);t.addedge(get_id_y(y),i,0);t.addedge(i,1,abs(x-fx)+abs(y-fy));//每個點都需要與終點單獨連一下邊}t.Dijkstra(0);printf("%lld\n",t.d[1]);return 0;
}
