讨论 / MZoier ggbbgg
ggbbgg 2016-02-29 18:34:50
点我顶贴 收藏 删除
#include<cstdio>

#include<queue>

#include<cmath>

#include<cstring>

using namespace std;

int v,n;

const double INF = 10000000.00;

struct edge{

int to;

double t;

edge* next;

};

edge* head[101];

int x[101],y[101];

double d[101];

double dis(int i,int j){

int dx = x[i]-x[j],dy = y[i] - y[j];

return sqrt(dx * dx + dy * dy);

}

double g(int i,int j){

return sqrt((y[j]-y[i])*2/10.0);

}

void adde(int s,int e,double w)

{

edge* ne = new edge();

ne->t = w;

ne->to = e;

ne->next = head[s];

head[s] = ne;

}

void dij()

{

typedef pair<double,int>pii;

priority_queue< pii,vector<pii>,greater<pii> >q;

q.push(make_pair(d[1],1));

while(!q.empty())

{

pii u = q.top();q.pop();

int k = u.second;

if(d[k]!=u.first) continue;

for(edge* i = head[k];i != NULL;i = i->next)

{

int p = i->to;

if(d[p] > d[k]+(i->t))

{

d[p]=d[k]+(i->t);

q.push(make_pair(d[p],p));

}

}

}

}

int main()

{

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

int f;

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

{

scanf("%d%d%d",&x[i],&y[i],&f);

if(f)

{

adde(f,i,dis(i,f)/v);

adde(i,f,dis(i,f)/v);

}

d[i] = INF;

}

d[1] = 0;

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

{

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

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

adde(j,i,g(i,j));

}

}

dij();

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

return 0;

}

#1 JessicaKrystal@2016-02-29 18:41:51
回复 删除
这个是智捅马蜂窝 86 的题解= =
#2 deadpool66@2016-02-29 18:49:59
回复 删除
...
#3 chen2000@2016-02-29 18:52:03
回复 删除
郭神又开始发福利了
#4 deadpool66@2016-02-29 22:53:16
回复 删除
郭神发福利
#5 12345671c@2016-02-29 23:16:39
回复 删除
86的题解发在这里。。。。。。。
查看更多回复
提交回复