讨论 / ZXY的题解
mzyczxy 2019-01-27 10:43:58
点我顶贴 收藏 删除
此题有坑。

主要是建图很麻烦。

步骤:

1、首先从2到n枚举点,因为他们都有父亲,建立双向边。

2、然后,用一个O(n^2)的算法枚举所有点,看有没有可以跳跃的(即:xi==xj&&yi>yj),建立单向边。注意:只能从上往下跳。

3、跑一遍dij完事。

代码:(拒绝抄题解)

#include<bits/stdc++.h>

using namespace std;

#undef y1

priority_queue<pair<double,int> >q;

int n,v;

struct node {

double x,y;

int fa;

}a[105];

struct Edge {

int to,next;

double dis;

}edge[1000005];

int k=1;

int head[105];

double d[105];

bool vis[105];

inline void Dijskra()

{

for(register int i=1;i<=105;i++) {

d[i]=1000000000.1415926;

}

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

d[1]=0;

q.push(make_pair(0,1));

while(q.size()) {

int p=q.top().second;q.pop();

if(vis[p]) continue;

vis[p]=1;

for(register int i=head[p];i;i=edge[i].next) {

int x=edge[i].to;

double y=edge[i].dis;

if(d[x]>d[p]+y) {

d[x]=d[p]+y;

q.push(make_pair(-d[x],x));

}

}

}

}

inline double distance(double x1,double y1,double x2,double y2)

{

return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

inline void Read()

{

cin>>n>>v;

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

cin>>a[i].x;

cin>>a[i].y;

cin>>a[i].fa;

}

}

inline void Add_Edge(int from,int to,double dis)

{

edge[k].to=to;

edge[k].dis=dis;

edge[k].next=head[from];

head[from]=k;

k++;

}

inline void build()

{

for(register int i=2;i<=n;i++) {

int f=a[i].fa;

double x1=a[i].x;

double y1=a[i].y;

double x2=a[f].x;

double y2=a[f].y;

double dis=distance(x1,y1,x2,y2)/v*1.0;

Add_Edge(i,f,dis);

Add_Edge(f,i,dis);

}

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

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

if(i==j) continue;

else {

if(a[i].x==a[j].x&&a[j].y<a[i].y) {

double dis=sqrt((a[i].y-a[j].y)*2/10.0);

Add_Edge(i,j,dis);

}

}

}

return;

}

int main()

{

Read();

build();

Dijskra();

cout<<fixed<<setprecision(2)<<d[n]<<endl;

}

#1 mzyczly@2019-01-27 17:18:36
回复 删除
沙发
#2 mzyczqazqn@2019-01-27 17:18:43
回复 删除
前排兜售各种零食
#3 mzyczly@2019-01-27 17:19:16
回复 删除
楼上是傻逼(同zxy)
#4 mzyczqazqn@2019-01-27 17:19:56
回复 删除
楼上是傻逼(同zxy)
查看更多回复
提交回复