**题意：

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

思路：

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

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

#include
#include
#include
#include
#include

#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;
queueq;
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; }