hdu2482 字典树+spfa

题意：

给你一个地图，地图上有公交站点和路线，问你从起点到终点至少要换多少次公交路线。

思路：

首先上面的题意说的和笼统，没说详细是因为这个题目叙述的很多，描述起来麻烦，

下面说思路，做这个题首先我们要把起点和终点的坐标求出来，每次点击地图我都是记录当前现则框的坐上角坐标，最后确定图之后再加上给的x,y转换后的实际位置，这样就的到了精准的位置，然后建图，题目让求的是换车次数，而题目给的是路径，所以我们要把每个路径都拆成任意边，比如 a -> b - > c 要拆成 a - b ,a - c ,b - c这三条，然后在起点和终点根据限制加进来，因为距离都是1可以最短路也可以广搜，（广搜速度会快点），我写的是最短路，这个无所谓，还有一个关键的地方就是hash车站地点，一开始我用的map果断超时了，因为map的操作是设计到排序的，所以超时了，（然后就没有去优化map,其实可以用vector，或者别的不设计到排序的容器，自己STL会的不是很多所以就没尝试去用）最后我是直接写了一个字典树，虽然有点麻烦，但没难度，所以就用字典树去hash名字吧，具体看代码。

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<queue>

#define N_node 5500

#define N_edge 100000

#define INF 1000000000



using namespace std;

typedef struct

{

   int to ,next ,cost;

}STAR;

typedef struct

{

   double x ,y;

}NODE;

typedef struct Tree

{

   Tree *next[26];

   int v;

}Tree;

Tree root;

STAR E[N_edge];

NODE node[N_node];

int list[N_node] ,tot;

int s_x[N_node];

double dir[4][2] = {0 ,0 ,0 ,0.5 ,0.5 ,0 ,0.5 ,0.5};

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

{

   E[++tot].to = b;

   E[tot].cost = c;

   E[tot].next = list[a];

   list[a] = tot;

   E[++tot].to = a;

   E[tot].cost = c;

   E[tot].next = list[b];

   list[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);

   return sqrt(x + y);

}

NODE Get_se(char str[] ,double x ,double y)

{

   NODE ans;

   ans.x = ans.y = 0;

   double now = 10240;

   for(int i = 0 ;i < 8 ;i ++)

   {

      ans.x += now * dir[str[i] - '0'][0];

      ans.y += now * dir[str[i] - '0'][1];

      now /= 2;

   }

   ans.x += 10240 / pow(4.0 ,7.0) * x;

   ans.y += 10240 / pow(4.0 ,7.0) * y;

   return ans;

}

void spfa(int s ,int n)

{

   int mark[N_node] = {0};

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

   s_x[i] = INF;

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

   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);

            }

         }

      }

   }

   return ;

}

void Buid_Tree(char *str ,int now)

{

   int len = strlen(str);

   Tree *p = &root ,*q;

   for(int i = 0 ;i < len ;i ++)

   {

      int id = str[i] - 'a';

      if(p -> next[id] == NULL)

      {

         q = (Tree *)malloc(sizeof(root));

         //q -> v;

         for(int j = 0 ;j < 26 ;j ++)

         q -> next[j] = NULL;

         p -> next[id] = q;

         p = p -> next[id];

      }

      else

      p = p -> next[id];

   }

   p -> v = now;

}

int Find(char *str)

{

   int len = strlen(str);

   Tree *p = &root;

   for(int i = 0 ;i < len ;i ++)

   {

      int id = str[i] - 'a';

      p = p -> next[id];

   }

   return p -> v;

}

int main ()

{

   int t ,n ,m ,k ,i ,j;

   double x ,y;

   char str[50];

   NODE s ,e;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%s %lf %lf" ,str ,&x ,&y);

      s = Get_se(str ,x ,y);

      scanf("%s %lf %lf" ,str ,&x ,&y);

      e = Get_se(str ,x ,y);

      int nowid = 2;

      scanf("%d" ,&n);

      for(i = 0 ;i < 26 ;i ++)

      root.next[i] = NULL;

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

      {

         scanf("%s %lf %lf" ,str ,&node[i+2].x ,&node[i+2].y);

         Buid_Tree(str ,++nowid);

      }

      scanf("%d" ,&m);

      char tmp[33][22];

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

      while(m--)

      {

         scanf("%d" ,&k);

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

         scanf("%s" ,tmp[i]);

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

         for(j = i + 1 ;j <= k ;j ++)

         add(Find(tmp[i]) ,Find(tmp[j]) ,1);

      }

      if(Get_dis(s ,e) <= 2000)

      {

         puts("walk there");

         continue;

      }

      for(i = 3 ;i <= nowid ;i ++)

      {

         if(Get_dis(s ,node[i]) <= 1000) add(1 ,i ,1);

         if(Get_dis(e ,node[i]) <= 1000) add(2 ,i ,1);

      }

      spfa(1 ,nowid);

      s_x[2] == INF ? puts("take a taxi") : printf("%d\n" ,s_x[2] - 2);

   }

   return 0;

}

巴特西

hdu2482 字典树+spfa

最新文章

热门文章