题目
题目大意
轨道交通网络由 2n 条地铁线路构成，组成了一个 n 纵 n 横的交通网。如下图所示，这 2n 条线路每条线路都包含 n 个车站，而每个车站都在一组纵横线路的交汇处。
并非每个车站都能够进行站内换乘，能够进行站内换乘的地铁站共有 m 个，在下图中，标上方块标记的车站为换乘车站。已知地铁运行 1 站需要 2 分钟，而站内换乘需要步行 1 分钟。
在不中途出站的前提下，从学校回家最快需要多少时间（等车时间忽略不计）。
题目解析
很明显是一个最短路，主要是在构图上需要解决
把换乘车站（包括起点和终点）的坐标分为2个点，一个点连纵坐标相同的点，另一个点连横坐标相同的点，距离为2点的距离，而同属一个坐标的两个点的距离为1（起点和终点为0）
在这样构图以后，跑一个最短路即可
代码
#include<bits/stdc++.h>
using namespace std;
struct A
{int x,y,id;
}a[200005];
struct V
{int s,i;
};
vector<V> dis[200005];
queue<int> q;
int n,m,f[200005];
bool flag[200005];
void add1(int x)
{V s;s.s=2*(a[x+1].y-a[x].y);s.i=a[x+1].id;dis[a[x].id].push_back(s);s.i=a[x].id;dis[a[x+1].id].push_back(s);
}
void add2(int x,int p)
{V s;s.s=2*(a[x+1].x-a[x].x);s.i=a[x+1].id+p;dis[a[x].id+p].push_back(s);s.i=a[x].id+p;dis[a[x+1].id+p].push_back(s);
}
bool cmp1(A a,A b)
{return a.x==b.x?a.y<b.y:a.x<b.x;
}
bool cmp2(A a,A b)
{return a.y==b.y?a.x<b.x:a.y<b.y;
}
int main()
{cin>>n>>m;for(int i=1;i<=m+2;i++){cin>>a[i].x>>a[i].y;a[i].id=i;a[i+m+2]=a[i];a[i+m+2].id=i+m+2;V s;if(i>m) s.s=0;else s.s=1;s.i=i+m+2;dis[i].push_back(s);s.i=i;dis[i+m+2].push_back(s);}sort(a+1,a+m+3,cmp1);for(int i=1;i<m+2;i++)if(a[i].x==a[i+1].x)add1(i);sort(a+1,a+m+3,cmp2);for(int i=1;i<m+2;i++)if(a[i].y==a[i+1].y)add2(i,m+2);q.push(m+1);memset(f,0x3f,sizeof(f));f[m+1]=0;while(!q.empty()){int id=q.front();q.pop();flag[id]=0;for(int i=0;i<dis[id].size();i++){if(f[id]+dis[id][i].s<f[dis[id][i].i]){f[dis[id][i].i]=f[id]+dis[id][i].s;if(!flag[dis[id][i].i]){q.push(dis[id][i].i);flag[dis[id][i].i]=1; }}}}if(f[2*m+4]==f[0])cout<<-1;elsecout<<f[2*m+4];return 0;
}
