1 条题解
-
0

#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
- 上传者