学步园

 一道相当题目描述相当扯的题。

这道题目的描述最后说的是求出到达最后一个点的最短距离，所以输入数据最后输入的城堡的坐标是没用的。

就是先求出两点之间的距离，若不大于村落间距离，并且不大于最后的距离限制 l ，则在两点间建边。

最后任意方法求出最短路即可。

 
#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define eps 1e-9
#define zero(x) (fabs(x)<eps?0:x)
#define maxn 110
double mp[maxn][maxn];
double divs[maxn];
int vis[maxn];
struct node
{
    int x,y,r;
} p[maxn];

double con(node a,node b)
{
    double len;
    len=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    return len;
}

int n;
double dij()
{
    for(int i=0; i<=n; i++)
        divs[i]=mp[0][i];
    divs[0]=0.0;
    vis[0]=1;
    for(int i=1; i<n; i++)
    {
        double min=100000000.0;
        int t=-1;
        for(int j=0; j<n; j++)
            if(!vis[j]&&divs[j]<min)
                min=divs[j],t=j;
        //printf("--->%d  %.2lf\n",t,min);
        if(t==-1)
            return min;
        vis[t]=1;
        for(int j=0; j<n; j++)
            if(!vis[j]&&divs[j]>mp[t][j]+divs[t])
                divs[j]=mp[t][j]+divs[t];
    }
    return divs[n-1];
}
void  init()
{
    memset(vis,0,sizeof(vis));
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
            mp[i][j]=100000000.0;
        mp[i][i]=0.0;
    }
}
int main()
{
    //freopen("in1.txt","r",stdin);
    //freopen("in.txt","w",stdout);
    while(~scanf("%d",&n))
    {
        init();
        for(int i=0; i<n; i++)
            scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].r);
        int a,b;
        double l;
        scanf("%d%d%lf",&a,&b,&l);
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                double len=con(p[i],p[j]);
                //printf("--->%.2lf   %.21f    %.2lf\n",len,l,(double)(p[i].r+p[j].r));
                if((double)l-len>=0&&(double)(p[i].r+p[j].r)-len>=0)
                {
                    //printf("*****\n");
                    mp[i][j]=mp[j][i]=len;
                }
            }
        }
        double res=dij();
        if(res>=100000000.0)
            printf("GAME OVER.\n");
        else
            printf("%.6lf\n",res);
    }
    return 0;
}