題意：
? ? ? 給你一個地圖，地圖上有公交站點和路線，問你從起點到終點至少要換多少次公交路線。


思路：
? ? ? 首先上面的題意說的和籠統，沒說詳細是因為這個題目敘述的很多，描述起來麻煩，

下面說思路，做這個題首先我們要把起點和終點的坐標求出來，每次點擊地圖我都是記錄當前現則框的坐上角坐標，最后確定圖之后再加上給的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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。