rqnoj86 智捅马蜂窝

题目描述

背景

为了统计小球的方案数，平平已经累坏了。于是，他摘掉了他那800度的眼镜，躺在树下休息。

后来，平平发现树上有一个特别不一样的水果，又累又饿的平平打算去把它摘下来。

题目描述

现在，将大树以一个N个节点的无向图的形式给出，每个节点用坐标（Xi，Yi）来表示表示，平平要从第一个点爬到第N个点，除了从一个节点爬向另一个相邻的节点以外，他还有一种移动方法，就是从一个节点跳下，到达正下方的某个节点（之间可隔着若干个点和边），即当Xj=Xi and Yi<Yj 时，平平就可以从j节点下落到i节点，他下落所用时间满足自由落体公式，t=sqrt((Yj-Yi)*2/g) （注意：g取10）。如果出现两线相交的情况，我们不认为它们是相通的。

数据规模

对于100%数据,1<=N<=100,1<=V<=10,0<=X,Y<=100.

建议使用extended(pas)或double（c and c++）计算，我们对于精度造成的误差将不予重测。

输入格式

两个整数N,V，N表示节点个数，V表示平平爬树的速度。

接下来N行，每行包含3个整数X,Y,F，X,Y是这个点的坐标，F是他的父节点（F一定小于这个点的标号，第一行的F为0）。

注意：两节点间距离按欧几里德距离计算 dis = sqrt( ( x1 – x2 ) 2+ ( y1 – y2 )2 )

输出格式

输出仅包括一行，从1到N所用的最少所需时间T，保留两位小数。

样例输入

9 1
5 0 0
5 5 1
6 5 2
7 6 2
6 9 2
3 6 2
4 5 2
3 2 7
7 2 3

样例输出

8.13

暴力+spfa 注意是无向图

//Serene

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

using namespace std;

const int maxn=100+10;

double n,v;

struct Node{

    double x,y;int pos;

}node[maxn];

int fir[maxn],nxt[maxn*maxn],to[maxn*maxn],e=0;

double val[maxn*maxn];

void add(int x,int y,double z) {

	to[++e]=y;nxt[e]=fir[x];fir[x]=e; val[e]=z;

}

bool cmp(const Node& a,const Node& b) {

	return a.x==b.x? a.y>b.y:a.x<b.x;

}

double ds(int x,int y) {

	return sqrt((node[x].x-node[y].x)*(node[x].x-node[y].x)+(node[x].y-node[y].y)*(node[x].y-node[y].y));

}

double ff(int x,int y) {

	return sqrt((node[x].y-node[y].y)/5.0);

}

double dis[maxn];

int zz[maxn];

bool vis[maxn];

void spfa(int st) {

	memset(zz,0,sizeof(zz));

	memset(vis,0,sizeof(vis));

	for(int i=2;i<=n;++i) dis[i]=1e7;

	int s=1,t=0,x,y,z;

	zz[++t]=st;vis[st]=1;

	while(s<=t) {

		x=zz[s%maxn];

		for(y=fir[x];y;y=nxt[y]) {

			z=to[y];

			if(dis[z]<=dis[x]+val[y]) continue;

			dis[z]=dis[x]+val[y];

			if(!vis[z]) {

				vis[z]=1;t++;

				zz[t%maxn]=z;

			}

		}

		s++;vis[x]=0;

	}

}

int main() {

	scanf("%lf%lf",&n,&v);

	int z;

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

		node[i].pos=i;

		scanf("%lf%lf",&node[i].x,&node[i].y);

		scanf("%d",&z);

		if(z)add(z,i,ds(z,i)/v),add(i,z,ds(z,i)/v);

	}

	sort(node+1,node+(int)n+1,cmp);

	for(int i=1;i<=n;++i) for(int j=i+1;j<=n&&node[j].x==node[i].x;++j)

	add(node[i].pos,node[j].pos,ff(i,j));

	spfa(1);

	printf("%.2lf",dis[(int)n]);

	return 0;

}

巴特西

rqnoj86 智捅马蜂窝

最新文章

热门文章