P2903 [USACO08MAR]麻烦的干草打包机The Loathesome Hay Baler

传送门

题目问的是从出发点一直跑到终点的一条链上所有齿轮的速度和

其他的不用考虑

直接搜就好了

注意求的是绝对值之和，不是和的绝对值，所以不用考虑方向问题

注意 N<=1050 数组不要只开1007！

代码简单不注释

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=;

int n,st,ed;

int pos[N][],r[N];

double ans;

inline double f(int a,int b)

{

    double x=pos[a][]-pos[b][],y=pos[a][]-pos[b][];

    return sqrt(x*x+y*y);

}

int fir[N],from[N<<],to[N<<],cnt;

inline void add(int &a,int &b)

{

    from[++cnt]=fir[a];

    fir[a]=cnt; to[cnt]=b;

}

bool vis[N];

void dfs(int x,double res,double v)

{

    if(x==ed) { ans=res; return; }

    vis[x]=;

    for(int i=fir[x];i;i=from[i])

    {

        int &u=to[i]; if(vis[u]) continue;

        double vv=v*(double)r[x]/(double)r[u];

        dfs(u,res+vv,vv);

    }

}

int main()

{

    n=read(); pos[][]=read(); pos[][]=read();

    for(int i=;i<=n;i++)

    {

        pos[i][]=read(),pos[i][]=read(),r[i]=read();

        if(pos[i][]==&&pos[i][]==) st=i;

        if(pos[i][]==pos[][]&&pos[i][]==pos[][]) ed=i;

    }

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++)

            if(f(i,j)==(double)r[i]+(double)r[j]) add(i,j),add(j,i);

    dfs(st,10000.0,10000.0);

    printf("%d",(int)ans);

    return ;

}