首页 > 代码库 > （最短路+A*搜索）POJ 2449 - Remmarguts' Date
（最短路+A*搜索）POJ 2449 - Remmarguts' Date
题意：
给一个DAG，要求s到t的第K短路，很经典的问题。
分析：
我们可以看到k<=1000，这个值不是很大，我可以想到直接bfs走遍所有情况，最多也就有1000中情况，但是1000个点显然会M。
既然是要求k短路，也就是说最终计算出来的到达t的花费必然是递增的，也就是说我们在搜索的时候肯定要用到优先队列。
这时应该很明显了，必然需要A*搜索，但是A*的预估函数依然是个问题，我想了很久没有想到，后来偶然在一本书上发现了这题。
书上的处理是用dijsktra预处理每点到t的最短路，就是每个状态到达目标的预估值。
恍然大悟。
但是怎么求每个点到t的最短路的，我们知道dijsktra的中间变量dist计算的是s到每个顶点的最短路，我们只需要把原图构建一个反向图，
计算t到每个点的最短路，就是原图每个点到t的最短路，这时候再进行普通的A*就行了。
然而本题一堆坑。
1、你需要再A*的时候判连通，不然将死循环
2、需要特殊处理从自己走到自己的情况，初始的0显然不算在k短路内。
代码：
1 #include <set> 2 #include <map> 3 #include <list> 4 #include <cmath> 5 #include <queue> 6 #include <stack> 7 #include <vector> 8 #include <bitset> 9 #include <string> 10 #include <cctype> 11 #include <cstdio> 12 #include <cstring> 13 #include <cstdlib> 14 #include <iostream> 15 #include <algorithm> 16 // #include <unordered_map> 17 18 using namespace std; 19 20 typedef long long ll; 21 typedef unsigned long long ull; 22 typedef pair<int, int> pii; 23 typedef pair<ull, ull> puu; 24 25 #define inf (0x3f3f3f3f) 26 #define lnf (0x3f3f3f3f3f3f3f3f) 27 #define eps (1e-9) 28 #define fi first 29 #define se second 30 31 bool sgn(double a, string select, double b) { 32 if(select == "==")return fabs(a - b) < eps; 33 if(select == "!=")return fabs(a - b) > eps; 34 if(select == "<")return a - b < -eps; 35 if(select == "<=")return a - b < eps; 36 if(select == ">")return a - b > eps; 37 if(select == ">=")return a - b > -eps; 38 } 39 40 41 //-------------------------- 42 43 const ll mod = 1000000007; 44 const int maxn = 1010; 45 46 //use to bfs 47 struct Node { 48 int v, c; 49 Node(int _v = 0, int _c = 0) { 50 v = _v, c = _c; 51 } 52 bool operator<(const Node &a)const { 53 return c > a.c; 54 } 55 }; 56 57 //first is ‘v‘ , second is ‘cost‘ 58 vector<pii> edge[maxn]; 59 vector<pii> zedge[maxn]; 60 bool vis[maxn]; 61 int dist[maxn]; 62 63 void addedge(int u, int v, int w) { 64 edge[v].push_back(make_pair(u, w)); 65 zedge[u].push_back(make_pair(v, w)); 66 } 67 68 // id from 1 69 void dijkstra_heap(int n, int start) { 70 memset(vis, 0, sizeof(vis)); 71 for(int i = 1; i <= n; i++) dist[i] = inf; 72 priority_queue<Node> que; 73 while(!que.empty())que.pop(); 74 dist[start] = 0; 75 que.push(Node(start, 0)); 76 Node tmp; 77 while(!que.empty()) { 78 tmp = que.top(); 79 que.pop(); 80 int u = tmp.v; 81 if(vis[u])continue; 82 vis[u] = true; 83 for(int i = 0; i < edge[u].size(); i++) { 84 int v = edge[u][i].fi; 85 int cost = edge[u][i].se; 86 if(!vis[v] && dist[v] > dist[u] + cost) { 87 dist[v] = dist[u] + cost; 88 que.push(Node(v, dist[v])); 89 } 90 } 91 } 92 } 93 94 struct anode { 95 int v; 96 int f, g, h; 97 anode(int _v = 0, int _f = 0, int _g = 0, int _h = 0) { 98 v = _v, f = _f, g = _g, h = _h; 99 }100 bool operator<(const anode &a)const {101 return f > a.f;102 }103 };104 105 int n, m;106 int s, t, k;107 108 bool Astar(int start) {109 if(s == t) {110 k++;111 }112 if(dist[start] == inf) {113 return false;114 }115 priority_queue<anode> que;116 while(!que.empty())que.pop();117 int num = 0;118 que.push(anode(start, dist[start], 0, dist[start]));119 while(!que.empty()) {120 anode tmp = que.top();121 que.pop();122 if(tmp.v == t) {123 num++;124 // printf("%d\n", tmp.g );125 }126 if(num >= k) {127 printf("%d\n", tmp.g );128 return true;129 }130 int u = tmp.v;131 for(int i = 0; i < zedge[u].size(); i++) {132 int v = zedge[u][i].fi;133 int cost = zedge[u][i].se;134 int g = tmp.g + cost;135 int h = dist[v];136 int f = g + h;137 que.push(anode(v, f, g, h));138 }139 }140 return false;141 }142 143 144 void solve() {145 while(~scanf("%d%d", &n, &m)) {146 for(int i = 1; i <= n; i++) {147 edge[i].clear();148 zedge[i].clear();149 }150 int u, v, w;151 for(int i = 0; i < m; i++) {152 scanf("%d%d%d", &u, &v, &w);153 addedge(u, v, w);154 }155 scanf("%d%d%d", &s, &t, &k);156 dijkstra_heap(n, t);157 if(!Astar(s)) {158 puts("-1");159 }160 }161 }162 163 int main() {164 165 #ifndef ONLINE_JUDGE166 freopen("1.in", "r", stdin);167 freopen("1.out", "w", stdout);168 #endif169 // iostream::sync_with_stdio(false);170 solve();171 return 0;172 }
（最短路+A*搜索）POJ 2449 - Remmarguts' Date
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。