主要是建图很麻烦。
步骤：
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;
}