1 条题解

  • 0
    @ 2026-7-4 12:06:08

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int M = 105;
    #define int long long
    const int inf = 1e18;
    int read()
    {
    	int x=0,f=1;char c;
    	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
    	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    	return x*f;
    }
    int n,m,R,k1,k2,k3,ans,dp[M][M][M];
    struct node{int x,y,w;}a[M],b[M],c[M],d[M];
    int sqr(int x) {return x*x;}
    void upd(int &x,int y) {x=min(x,y);}
    int dis(node A,node B)
    {
    	return sqr(A.x-B.x)+sqr(A.y-B.y)<=R*R;
    }
    signed main()
    {
    	n=read();m=read();R=read();
    	for(int i=1;i<=n;i++)
    		a[i].x=read(),a[i].y=read();
    	for(int i=1;i<=m;i++)
    	{
    		int x=read(),y=read(),w=read();
    		if(y<0) b[++k1]={x,y,w};
    		else c[++k2]={x,y,w};
    	}
    	for(int i=1;i<=n;i++)
    	{
    		bool f=0;
    		for(int j=1;j<=k1;j++) f|=dis(a[i],b[j]);
    		for(int j=1;j<=k2;j++) f|=dis(a[i],c[j]);
    		if(f) d[++k3]=a[i];
    	}
    	auto cmp = [&] (node A,node B) {return A.x<B.x;};
    	sort(b+1,b+1+k1,cmp);
    	sort(c+1,c+1+k2,cmp);
    	sort(d+1,d+1+k3,cmp);
    	memset(dp,0x3f,sizeof dp);
    	ans=inf;dp[0][0][0]=0;
    	for(int i=1;i<=k3;i++) for(int j=0;j<=k1;j++)
    		for(int k=0;k<=k2;k++) if(dp[i-1][j][k]<inf)
    		{
    			int t=dp[i-1][j][k];
    			if((j && dis(d[i],b[j])) || 
    			(k && dis(d[i],c[k]))) upd(dp[i][j][k],t);
    			for(int l=j+1;l<=k1;l++) if(dis(d[i],b[l]))
    				upd(dp[i][l][k],t+b[l].w);
    			for(int l=k+1;l<=k2;l++) if(dis(d[i],c[l]))
    				upd(dp[i][j][l],t+c[l].w);
    		}
    	for(int i=0;i<=k1;i++) for(int j=0;j<=k2;j++)
    		upd(ans,dp[k3][i][j]);
    	printf("%lld\n%lld\n",k3,ans);
    }
    
    
    • 1

    信息

    ID
    5757
    时间
    3000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者