MLE求调
查看原帖
MLE求调
1346137
HJX_Shirley楼主2024/11/8 12:38
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int num,n,zx,zy,qd,zd,head[N],path[N];
double zs;
double ans;
bool vis[N];
struct edge{
    int next, to;
}e[N*N];
struct poi{
    int x, y, r;
}p[N];
void addEdge(int from,int to) {
    num++;
    e[num].next=head[from];
    e[num].to=to;
    head[from]=num;
}
bool xj(poi a,poi b){
    if(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))==a.r+b.r)return true;
    return false;
}
void bfs() {
    queue<int> q;
    q.push(qd);
    path[qd]=0;
    vis[qd]=true;
    while(!q.empty()){
        int x=q.front();
        for(int i=head[x];i!=0;i=e[i].next) {
            int y=e[i].to;
            if(!vis[y]){
            	vis[y]=true;
            	q.push(y);
            	path[y]=x;
            	if(y==zd)return ;
			}
        }
        q.pop();
    }
}
void ps(int zd) {
    if(zd==qd){
        zs=10000;
        ans+=zs;
    }
    else {
        ps(path[zd]);
        zs=zs*(p[path[zd]].r)/p[zd].r;
        ans+=zs;
    }
}
int main() {
    cin>>n>>zx>>zy;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y>>p[i].r;
        if(p[i].x==zx&&p[i].y==zy)zd=i;
        if(p[i].x==0&&p[i].y==0)qd=i;
    }
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(xj(p[i],p[j]))addEdge(i,j),addEdge(j,i);
    bfs();
    ps(zd);
    cout<<(int)ans;
    return 0;
}
2024/11/8 12:38
加载中...