求助prim
查看原帖
求助prim
496587
coding_felix楼主2022/4/4 20:20
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1200;
const int M=600;
const int MAXN=2e6+1000;
int n,m,ans;
int jump[M],x[N],y[N];
int ne,head[N],dis[N],mx=0;
bool vis[N];
struct edge{
	int v,w,nxt;
}e[MAXN];
struct Node{
	int dis,x;
	Node(){}
	Node(int _dis,int _x){
		dis=_dis;
		x=_x;
	}
	friend bool operator >(const Node &a,const Node &b){
		return a.dis>b.dis||(a.dis==b.dis&&a.x<b.x);
	}
};
void add_edge(int u,int v,int w){
	e[ne].v=v;e[ne].w=w;
	e[ne].nxt=head[u];
	head[u]=ne++;
}
priority_queue<Node,vector<Node>,greater<Node> > q;
signed main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		scanf("%lld",&jump[i]);
		jump[i]*=jump[i];
	}
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&x[i],&y[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int tx=(x[i]-x[j])*(x[i]-x[j]);
			int ty=(y[i]-y[j])*(y[i]-y[j]);
			int tmp=tx+ty;
			add_edge(i,j,tmp);
			add_edge(j,i,tmp);
		}
	}
	int cpn=1,u=1;
	memset(head,-1,sizeof(head));
	memset(dis,0x3f3f3f3f,sizeof(dis));
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		dis[v]=min(dis[v],w);
		q.push(Node(dis[v],v));
	}
	while(++cpn<=n){
		vis[u]=1;
		Node h=q.top();
		while(vis[h.x])q.pop();
		mx=max(mx,h.dis);
		u=h.x;
		q.pop();
		for(int i=head[u];i!=-1;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(!vis[v]&&dis[v]>w){
				dis[v]=w;
				q.push(Node(dis[v],v));
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(jump[i]>=mx){
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}
2022/4/4 20:20
加载中...