90分代码,蒟蒻求助
查看原帖
90分代码,蒟蒻求助
148184
Charser茶色楼主2020/8/28 17:00

第二个点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;
} 

谢谢各位大佬了!

2020/8/28 17:00
加载中...