P3831代码求调
  • 板块学术版
  • 楼主ztjp13
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/22 16:00
  • 上次更新2023/11/3 01:58:22
查看原帖
P3831代码求调
342941
ztjp13楼主2023/8/22 16:00

样例全对,但0分

求大神调

#include<bits/stdc++.h> 
using namespace std; 

const int N=2*200005;
const int M=2*1000005;

int n,m;
int edge[M],ver[M],head[N],Next[M];

int tot;
int d[N];
bool vis[N];

struct node{
	int x,y,id;
}a[M];

priority_queue<pair<int,int> >q;

inline int read(){
	int f=1,k=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(f=='-') f=-1;
		c=getchar(); 
	}
	while(c>='0'&&c<='9'){
		k=k*10+c-'0';
		c=getchar();
	}
	return f*k;
}

bool cmp1(node a,node b){
	return a.x<b.x;
}

bool cmp2(node a,node b){
	return a.y<b.y;
}

void add(int x,int y,int z){    
	edge[++tot]=z;ver[tot]=y;Next[tot]=head[x];head[x]=tot;
}

void dij(int id){
	memset(d,0x3f3f3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[id]=0;
	q.push(make_pair(0,id));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=true; 
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i],z=edge[i];
			if(d[y]>d[x]+z){
				d[y]=d[x]+z;
				q.push(make_pair(-d[y],y));
			}
		}
	}
}

signed main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		a[i].x=read();
		a[i].y=read();
		a[i].id=i;
		add(a[i].id,a[i].id+m+2,1);
		add(a[i].id+m+2,a[i].id,1);
	}
	a[m+1].x=read(); a[m+1].y=read(); a[m+1].id=m+1;
	a[m+2].x=read(); a[m+2].y=read(); a[m+2].id=m+2;
	int sta=a[m+1].id,end=a[m+2].id;
	add(sta,sta+m+2,0); add(sta+m+2,sta,0);
	add(end,end+m+2,0); add(end+m+2,end,0);
	sort(a+1,a+m+2+1,cmp1);
	for(int i=1;i<m+2;i++){
		if(a[i].x==a[i+1].x){
			int z=2*abs(a[i].y-a[i+1].y);
			add(a[i].id,a[i+1].id,z);
			add(a[i+1].id,a[i].id,z);
		}
	}
	sort(a+1,a+m+2+1,cmp2);
	for(int i=1;i<m+2;i++){
		if(a[i].y==a[i+1].y){
			int z=2*abs(a[i].x-a[i+1].x);
			add(a[i].id+m+2,a[i+1].id+m+2,z);
			add(a[i+1].id+m+2,a[i].id+m+2,z);
		}
	}
	dij(sta);
	if(d[end]==0x3f) printf("-1\n");
	else printf("%d\n",d[end]);
	return 0;
} 
2023/8/22 16:00
加载中...