第二个点WA了,自己看不出什么问题,,求助
代码:
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 800001
#define N 200001
using namespace std;
struct Edge{
int nex,to,weight;
}edge[M];
struct point{
int x,y,ID;
}a[N];
int n,m,tot=0,headlist[N],d[N],Start,End;
bool vis[N];
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void adds(int x,int y,int w){
edge[++tot].to=y;
edge[tot].nex=headlist[x];
edge[tot].weight=w;
headlist[x]=tot;
}
void ins(int x,int y,int w){adds(x,y,w);adds(y,x,w);}
bool cmp1(point a,point b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool cmp2(point a,point b){
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
void SPFA(int x){
memset(d,127/3,sizeof(d));
queue<int> q;
d[x]=0;vis[x]=true;q.push(x);
while(!q.empty())
{
int u=q.front();
q.pop();vis[u]=false;
for(int i=headlist[u];i;i=edge[i].nex)
{
int v=edge[i].to,w=edge[i].weight;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
if(!vis[v]){vis[v]=true;q.push(v);}
}
}
}
}
int main(){
n=read();m=read();Start=m+1;End=m+2;
for(int i=1;i<=m+2;i++)
{a[i].x=read();a[i].y=read();a[i].ID=i;}
sort(a+1,a+m+3,cmp1);
for(int i=1;i<=m+2;i++)
if(a[i].x==a[i+1].x) ins(a[i].ID,a[i+1].ID,2*(a[i+1].y-a[i].y));
sort(a+1,a+m+3,cmp2);
for(int i=1;i<=m+2;i++)
if(a[i].y==a[i+1].y) ins(a[i].ID+m+2,a[i+1].ID+m+2,2*(a[i+1].x-a[i].x));
for(int i=1;i<=m;i++)
ins(i,i+m+2,1);
ins(m+1,m*2+3,0);ins(m+2,m*2+4,0);
SPFA(Start);
if(d[End]==d[0]){printf("-1");return 0;}
printf("%d",d[End]);
return 0;
}
谢谢各位大佬了!