NYOJ 1276机器设备

Alpha 公司设计出一种节能的机器设备。它的内部结构是由 N 个齿轮组成。整个机器设备有 一个驱动齿轮，当启动它时，它立即按 10,000 圈/小时转速顺时针转动，然后它又带动与它相切 的齿轮反方向，即逆时针转动。齿轮之间互相作用，每个齿轮都可能驱动着多个齿轮，最终带动 一个工作齿轮完成相应的任务。 在这套设备中，记录了每个齿轮的圆心坐标和齿轮半径。已知驱动齿轮位于（0,0），最终的 工作齿轮位于（Xt, Yt）。 Alpha 公司想知道传动序列中所有齿轮的转速。所谓传动序列，即能量由驱动齿轮传送，最 后到达工作齿轮的过程中用到的所有齿轮。能量传送过程是，在一个半径为 R，转速为 S 圈/每小 时的齿轮的带动下，与它相切的半径为 R’的齿轮的转速为-S*R/R’ 转/小时。负号的意思是， 表 示按反方向转动。

已知，机器设备中除了驱动齿轮以外，所有齿轮都可能被另外某个齿轮带动，并且不会出现 2 个不同的齿轮带动同一个齿轮的情况。 你的任务是计算整个传动序列中所有齿轮的能量之和。即所有齿轮转速的绝对值之和。 

输入

第一行： T 表示以下有 T 组测试数据（1≤T ≤8）
对每组测试数据：
第 1 行： N Xt Yt （2≤N ≤1100）
接下来有 N 行， Xi Yi Ri 表示 N 个齿轮的坐标和半径 i=1,2,….,N
（ -5000 ≤Xi ，Yi ≤ 5000 3 ≤ Ri ≤ 1000 ）
坐标以及半径是整数

输出

每组测试数据，输出占一行，即所有齿轮转速的绝对值之和 在double范围内，输出整数部分

样例输入

1
4 32 54
0 30 20
0 0 10
32 54 20
-40 30 20

样例输出

20000

来源

上传者

队列应用，弄清楚从驱动齿轮到当前齿轮的能量之和就能写了。

#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<queue>
using namespace std;
struct node
{
    int x;
    int y;
    double z;
    int flag;
    double l;
    double temp;
}a[2005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        //vector<int>b[1105];
        int n,xt,yt,xx,yy,zz;
        int i,j;
        cin>>n>>xt>>yt;
        for(i=0;i<n;i++)
        {
            a[i].flag=0;//是否被标记
            a[i].temp=0;//能量初始化
            cin>>a[i].x>>a[i].y>>a[i].z;
            if(0==a[i].x&&0==a[i].y)
              xx=i;
        }
        queue<node>q;
        double ans=0;
        node ll,p;
        a[xx].l=10000;
        a[xx].temp=10000;
        int s=0,flag=0;
        a[xx].flag=1;
        q.push(a[xx]);
        while(!q.empty())
        {
            p=q.front();
            q.pop();
            if(p.x==xt&&p.y==yt)
            {
                int ff=p.temp;
                printf("%d\n",ff);//找到工作齿轮结束
                break;
            }
            for(i=0;i<n;i++)
            {
                if(a[i].flag==0&&sqrt((p.y-a[i].y)*(p.y-a[i].y)+(p.x-a[i].x)*(p.x-a[i].x))==a[i].z+p.z)
                {//如果没有被访问过并且与当前要出队的节点相切则入队，且从驱动齿轮到当前齿轮的能量为当前出队节点的能量加上当前入队节点的能量之和
                    a[i].l=p.l*p.z/a[i].z;
                    a[i].temp=p.temp+a[i].l;//容易弄错的地方
                    q.push(a[i]);
                    a[i].flag=1;
                }
            }
        }
    }
    return 0;
}