讨论 / Cxy from luogu 的题解
mzycchexinyv 2019-01-27 13:57:10
点我顶贴 收藏 删除
一道骚气的题目。

建图有坑就不说了,

更骚气的是输出必须要用两位的double。

搞得我硬是调了半小时数据类型。

题不难,具体来说,先读入再建图,套Dijkstra就行了。

最后上程序:

#include<iostream>

#include<cstring>

#include<cmath>

#include<queue>

#include<iomanip>

using namespace std;

typedef pair<double,long long> pii;//建立pair类型(堆优化)

priority_queue<pii,vector<pii>,greater<pii> >q;// 建立队列(堆优化)

long long head[100000],cnt=1;

double dis[100000];

struct sz{//结构体(储存读入数据)

long long f,h,x,y;

}e1[100000];

struct sss{//建链表(建链表)

long long x,y,next;

double v;

}e[100000];

void add(long long x,long long y,double j)//向e链表加入数据

{

e[cnt].x=x;

e[cnt].y=y;

e[cnt].v=j;

e[cnt].next=head[x];

head[x]=cnt;

cnt++;

}

void Dijkstra()// Dijkstra算法求最小路径(模板不多说了)

{

memset(dis,9999999,sizeof(dis));//这里很坑,初始化dis数组的值要尽量大,表示为此改过三次

dis[1]=0;

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

while(!q.empty())

{

long long temp=q.top().second;

q.pop();

for(long long i=head[temp];i!=-1;i=e[i].next)

{

if(dis[e[i].y]>dis[temp]+e[i].v)

{

dis[e[i].y]=dis[temp]+e[i].v;

q.push(make_pair(dis[e[i].y],e[i].y));

}

}

}

}

int main()

{

long long n;

double m;

cin>>n>>m;

memset(head,-1,sizeof(head));//初始化head数组

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

{

cin>>e1[i].x>>e1[i].y>>e1[i].f;

e1[i].h=i;

}

for(long long i=1;i<=n;i++)//处理读入数据

{

long long x,y;

double j;

x=e1[i].h;//第一情况

y=e1[i].f;

j=double(sqrt(pow(double(e1[i].x-e1[e1[i].f].x),2)+pow(double(e1[i].y-e1[e1[i].f].y),2))/m);

add(x,y,j);//加入

add(y,x,j);

for(long long l=1;l<=n;l++)//第二情况

{

if(e1[i].x==e1[l].x&&e1[i].y>e1[l].y)

{

x=e1[i].h;

y=e1[l].h;

j=sqrt(double(e1[i].y-e1[l].y)*2/10);

add(x,y,j);//因为从树上跳下,所以只加一次

}

}

}

Dijkstra();

cout<<fixed<<setprecision(2)<<dis[n];

}

(确实很长我知道)

#1 mzyczly@2019-01-27 14:36:34
回复 删除
SB from cxy
查看更多回复
提交回复