hdu4179 限制最短路

题意：

这个题目估计读懂题意就ok了，关键是题意蛋疼，像我这样的英语渣渣活着可真难啊，题意大体是这样，给你n个点m条无向边，给你起点和终点，让你求从起点到终点的最短路径，其中有一些限制：

（1）所有的边的d必须小于等于题目给的D

（2）必须至少有一条边的d 等于题目给的 D

下面说一下d的求法，对于每条边ab,如果a.z >= b.z也就是下坡，d = 0,否则d等于高度变化的绝对值*100 除以线段在xoy面上的投影线段的长度，最后向下取证（不用考虑竖直上下的情况）。

思路：

题意懂了这个题目就好做了，直接判断建图，建两个图，一个是正向的一个是反向的，然后跑两边最短路，然后在枚举每一条d == D 的边取得最优的就行了。

#include<stdio.h>

#include<string.h>

#include<queue>

#include<math.h>

#define N_node 11111

#define N_edge 55555

#define INF 1000000000



using namespace std;

typedef struct

{

   int to ,next;

   double cost;

}STAR;

typedef struct

{

   int a ,b;

}EDGE;

typedef struct

{

   double x ,y ,z;

}NODE;

STAR E1[N_edge] ,E2[N_edge];

EDGE edge[N_edge] ,ee[N_edge];

NODE node[N_node];

int list1[N_node] ,list2[N_node] ,tot;

double dis1[N_node] ,dis2[N_node];

void add(int a ,int b ,double c)

{

   E1[++tot].to = b;

   E1[tot].cost = c;

   E1[tot].next = list1[a];

   list1[a] = tot;

   E2[tot].to = a;

   E2[tot].cost = c;

   E2[tot].next = list2[b];

   list2[b] = tot;

}

double get_dis(NODE a ,NODE b)

{

   double x = (a.x - b.x) * (a.x - b.x);

   double y = (a.y - b.y) * (a.y - b.y);

   double z = (a.z - b.z) * (a.z - b.z);

   return sqrt(x + y + z);

}

int get_d(NODE a ,NODE b)

{

    if(a.z >= b.z) return 0;

    double x = (a.x - b.x) * (a.x - b.x);

    double y = (a.y - b.y) * (a.y - b.y);

    double z = b.z - a.z;

    return int(z * 100 / sqrt(x + y));

}

void spfa(int s ,int n ,int list[] ,double s_x[] ,STAR E[])

{

   int mark[N_node] = {0};

   for(int i = 0 ;i <= n ;i ++) s_x[i] = INF;

   s_x[s] = 0 ,mark[s] = 1;

   queue<int>q;

   q.push(s);

   while(!q.empty())

   {

      int xin ,tou;

      tou = q.front();

      q.pop();

      mark[tou] = 0;

      for(int k = list[tou] ;k ;k = E[k].next)

      {

         xin = E[k].to;

         if(s_x[xin] > s_x[tou] + E[k].cost)

         {

            s_x[xin] = s_x[tou] + E[k].cost;

            if(!mark[xin])

            {

               mark[xin] = 1;

               q.push(xin);

            }

         }

      }

   }

}

int main ()

{

   int n ,m ,i ,s ,t ,d ,a ,b;

   while(~scanf("%d %d" ,&n ,&m) && n + m)

   {

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

      scanf("%lf %lf %lf" ,&node[i].x ,&node[i].y ,&node[i].z);

      for(i = 1 ;i <= m ;i ++)

      scanf("%d %d" ,&ee[i].a ,&ee[i].b);

      scanf("%d %d %d" ,&s ,&t ,&d);

      memset(list1 ,0 ,sizeof(list1));

      memset(list2 ,0 ,sizeof(list2)) ,tot = 1;

      int edge_t = 0;

      for(i = 1 ;i <= m ;i ++)

      {

         a = ee[i].a ,b = ee[i].b;

         int d1 = get_d(node[a] ,node[b]);

         int d2 = get_d(node[b] ,node[a]);

         double dis = get_dis(node[a] ,node[b]);

         if(d1 <= d) add(a ,b ,dis);

         if(d2 <= d) add(b ,a ,dis);

         if(d1 == d)

         {

            edge[++edge_t].a = a;

            edge[edge_t].b = b;

         }

         if(d2 == d)

         {

            edge[++edge_t].a = b;

            edge[edge_t].b = a;

         }

      }

      spfa(s ,n ,list1 ,dis1 ,E1);

      spfa(t ,n ,list2 ,dis2 ,E2);

      double ans = INF;

      for(i = 1 ;i <= edge_t ;i ++)

      {

         double now = dis1[edge[i].a] + get_dis(node[edge[i].a] ,node[edge[i].b]) + dis2[edge[i].b];

         if(ans > now) ans = now;

      }

      ans == INF ? puts("None") : printf("%.1lf\n" ,ans);

   }

   return 0;

}

巴特西

hdu4179 限制最短路

最新文章

热门文章