[题解]RQNOJ PID86 智捅马蜂窝

链接：http://www.rqnoj.cn/problem/86

思路：单源点最短路

建图：首先根据父子关系连双向边，边权是距离/速度；再根据跳跃关系连单向边，边权是自由落体的时间（注意自由下落是一个匀加速过程，若中途停下再跳一定没有直接跳优）。

我的实现：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <queue>
  7 using namespace std;
  8 #define MaxN 120
  9 #define MaxM 320
 10 #define INF 100000
 11 struct P
 12 {
 13     int v,x,y;
 14 }Point[MaxN];
 15 struct node
 16 {
 17     int v;
 18     double dist;
 19     node *next;
 20 };
 21 node Edge[MaxM];
 22 node *cnt=&Edge[0];
 23 node *adj[MaxN];
 24 double Dist[MaxN];
 25 int N,V;
 26 inline void Get_int(int &Ret)
 27 {
 28     char ch;
 29     bool flag=false;
 30     for(;ch=getchar(),ch<'0'||ch>'9';)
 31         if(ch=='-')
 32             flag=true;
 33     for(Ret=ch-'0';ch=getchar(),ch>='0'&&ch<='9';Ret=Ret*10+ch-'0');
 34     flag&&(Ret=-Ret);
 35 }
 36 inline double Dis(int a,int b)
 37 {
 38     double dx=(double)(Point[a].x-Point[b].x);
 39     double dy=(double)(Point[a].y-Point[b].y);
 40     return sqrt(dx*dx+dy*dy);
 41 }
 42 inline void Addedge(int u,int v,double w)
 43 {
 44     node *p=++cnt;
 45     p->v=v;
 46     p->dist=w;
 47     p->next=adj[u];
 48     adj[u]=p;
 49 }
 50 bool Cmp(P a,P b)
 51 {
 52     return ((a.x<b.x)||(a.x==b.x&&a.y<b.y));
 53 }
 54 inline void Read_Build()
 55 {
 56     Get_int(N); Get_int(V);
 57     int i,j,pos,fa;
 58     double T;
 59     for(i=1;i<=N;++i)
 60     {
 61         Get_int(Point[i].x);Get_int(Point[i].y);
 62         Point[i].v=i;
 63         Get_int(fa);
 64         if(!fa) continue;
 65         T=Dis(i,fa)/(double)V;
 66         Addedge(i,fa,T); Addedge(fa,i,T);
 67     }
 68     sort(Point+1,Point+N+1,Cmp);
 69     for(i=2;i<=N;i++)
 70     {
 71         if(Point[i].x!=Point[i-1].x)
 72         {
 73             pos=i;
 74         }
 75         else
 76         {
 77             for(j=pos;j<i;j++)
 78             {
 79                 T=sqrt((double)(Point[i].y-Point[j].y)/5.0);
 80                 Addedge(Point[i].v,Point[j].v,T);
 81             }
 82         }
 83 
 84     }
 85 }
 86 struct cmp
 87 {
 88     bool operator()(node a,node b)
 89     {
 90         return a.dist>b.dist;
 91     }
 92 };
 93 priority_queue <node, vector<node>, cmp> q;
 94 void Dijkstra(int s)
 95 {
 96     node c,d,*p;
 97     int u,v;
 98     for(int i=1;i<=N;i++)
 99         Dist[i]=INF;
100     Dist[s]=0;
101     c.v=s;c.dist=0;
102     q.push(c);
103     while(!q.empty())
104     {
105         d=q.top();q.pop();
106         u=d.v;
107         for(p=adj[u];p!=NULL;p=p->next)
108         {
109             v=p->v;
110             if(Dist[v]>Dist[u]+p->dist)
111             {
112                 Dist[v]=Dist[u]+p->dist;
113                 d.v=v;d.dist=Dist[v];
114                 q.push(d);
115             }
116         }
117     }
118 }
119 int main()
120 {
121     Read_Build();
122     Dijkstra(1);
123     printf("%.2lf
",Dist[N]);
124     return 0;
125 }

View Code