求助,只得了4点的10分
查看原帖
求助,只得了4点的10分
358763
江宁12345678楼主2023/4/25 22:23
#include<bits/stdc++.h>
using namespace std;
int n,m,c,xq,xz,yq,yz,idx,dist[111111],head[111111];
typedef pair<int,int> pr;
priority_queue<pr,vector<pr>,greater<pr> >smallH;
bool vis[111111];
struct stop
{
	int x,y,z;
};
stop hcz[222222];  
struct Node
{
	int to,nxt,w;
};
Node edge[666666];
bool cmph(stop x1,stop x2)
{
	if(x1.x==x2.x)
	{
		return x1.y<x2.y;
	}
	return x1.x<x2.x;
}
bool cmpz(stop y1,stop y2)
{
	if(y1.y==y2.y)
	{
		return y1.x<y2.x;
	}
	return y1.y<y2.y;
}
void add(int u,int v,int w)
{
	edge[idx].to=v;
	edge[idx].w=w;
	edge[idx].nxt=head[u];
	head[u]=idx++;	
} 
void dijkstra(int u)
{
	memset(dist,0x3f,sizeof(dist));
	dist[u]=0;	
	smallH.push({0,u});
	while(!smallH.empty())
	{
		pr node=smallH.top();
		smallH.pop();
		int d=node.first,id=node.second;
		if(vis[id])
		{
			continue;
		}
		vis[id]=true;
		for(int j=head[id];j!=-1;j=edge[j].nxt)
		{
			int v=edge[j].to;
			if(dist[v]>dist[id]+edge[j].w)
			{
				dist[v]=dist[id]+edge[j].w;
				smallH.push({dist[v],v});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(head,-1,sizeof(head));
	cin>>n>>m;
	int xx,yy;
	for(int i=1;i<=m;i++)
	{
		cin>>xx>>yy;
		hcz[i].x=xx;
		hcz[i].y=yy;
		hcz[i].z=i;
	}
	cin>>xq>>yq>>xz>>yz;
	for(int i=1;i<=m;i++)
	{
		add(hcz[i].z,hcz[i].z+m+2,1); 
		add(hcz[i].z+m+2,hcz[i].z,1); 
	}
	hcz[m+1].x=xq;hcz[m+1].y=yq;hcz[m+1].z=m+1;	
	add(hcz[m+1].z,hcz[m+1].z+m+2,0);
	add(hcz[m+1].z+m+2,hcz[m+1].z,0);
	hcz[m+2].x=xz;hcz[m+2].y=yz;hcz[m+2].z=m+2;
	add(hcz[m+2].z,hcz[m+2].z+m+2,0);
	add(hcz[m+2].z+m+2,hcz[m+2].z,0);
	sort(hcz+1,hcz+3+m,cmph);
	for(int i=2;i<=m+2;i++)
	{
		if(hcz[i].x==hcz[i-1].x)
		{
			add(hcz[i-1].z,hcz[i].z,2*(hcz[i].y-hcz[i-1].y));
			add(hcz[i].z,hcz[i-1].z,2*(hcz[i].y-hcz[i-1].y));
		}
	}
	sort(hcz+1,hcz+3+m,cmpz);
	for(int i=2;i<=m+2;i++)
	{
		if(hcz[i].y==hcz[i-1].y)
		{
			add(hcz[i-1].z+m+2,hcz[i].z+m+2,2*(hcz[i].x-hcz[i-1].x));
			add(hcz[i].z+m+2,hcz[i-1].z+m+2,2*(hcz[i].x-hcz[i-1].x));
		}
	}
	dijkstra(m+1);
	if(dist[m+2]>=0x3f)
	{
		cout<<"-1";
		return 0;
	}
	cout<<dist[m+2];
	return 0;	
} 
2023/4/25 22:23
加载中...