题意：在一个二维平面上，给你一个起点和终点，有一些车站，每次只能在车站下车，上车，或者换乘，每次换乘的时间是1，地铁不会拐弯，每次只会直线走，问你能否做地铁到达终点，如果不能打印-1
思路：有点分层图的思想，我们把横和纵的地铁先分为两层，然后直接建边，我们在第一层对第二层的连边就是换乘花费1（敲有趣的）
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=1200100; const int maxm=1200100; int cnt; struct node { int from,to,val,next; }edge[maxm<<1]; int head[maxm]; LL dis[maxn]; int vis[maxn]; struct Node { int val,id; bool operator <(const Node &b)const { if(val==b.val)return id<b.id; return val>b.val; } }; void init() { memset(head,-1,sizeof(head)); cnt=1; } void addedge(int from,int to,int val) { edge[cnt].from=from; edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } LL res; void dijkstra(int s,int e) { memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis)); res=dis[e]; Node now; priority_queue<Node>q; while(q.size())q.pop(); now.val=0,now.id=s; dis[s]=0; q.push(now); while(!q.empty()){ Node u=q.top(); q.pop(); if(vis[u.id])continue; vis[u.id]=1; for(int i=head[u.id];i!=-1;i=edge[i].next){ int to=edge[i].to; if(dis[u.id]+edge[i].val<dis[to]){ dis[to]=dis[u.id]+edge[i].val; Node pus; pus.id=to,pus.val=dis[to]; q.push(pus); } } } return ; } struct point { int x,y,id; }; point p[100005]; bool cmp1(point a,point b){ return (a.x<b.x)||(a.x==b.x&&a.y<b.y); } bool cmp2(point a,point b){ return (a.y<b.y)||(a.y==b.y&&a.x<b.x); } int main() { int n=read(),m=read(); int s=m+1,t=m+2; m+=2; init(); for(int i=1;i<=m;i++){ p[i].x=read(); p[i].y=read(); p[i].id=i; } sort(p+1,p+1+m,cmp1); for(int i=1;i<m;i++){ if(p[i].x==p[i+1].x){ addedge(p[i].id,p[i+1].id,(p[i+1].y-p[i].y)*2); addedge(p[i+1].id,p[i].id,(p[i+1].y-p[i].y)*2); } } sort(p+1,p+1+m,cmp2); for(int i=1;i<m;i++){ if(p[i].y==p[i+1].y){ addedge(p[i].id+m,p[i+1].id+m,(p[i+1].x-p[i].x)*2); addedge(p[i+1].id+m,p[i].id+m,(p[i+1].x-p[i].x)*2); } } for(int i=1;i<=m;i++){ addedge(p[i].id,p[i].id+m,1); addedge(p[i].id+m,p[i].id,1); } addedge(s,s+m,0);addedge(s+m,s,0); addedge(t,t+m,0);addedge(t+m,t,0); dijkstra(s,t); if(dis[t]==res)puts("-1"); else printf("%lld ",dis[t]); return 0; }