A*双向算法c++代码

以下是A*双向搜索的C++代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int M = 2e6 + 5;

struct Edge {
    int to, w, nxt;
} e[M << 1];

int head[N], tot;
int n, m, s, t;
int vis[N], dis[N], g[N], f[N];
int que[N], top, tail;

inline void add(int u, int v, int w) {
    e[++tot].to = v;
    e[tot].w = w;
    e[tot].nxt = head[u];
    head[u] = tot;
}

inline void spfa(int s, int *dis, int *h) {
    top = 0, tail = 1;
    que[1] = s;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0, h[s] = 0;
    while (top < tail) {
        int u = que[++top];
        vis[u] = 0;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                h[v] = h[u] + 1;
                if (!vis[v]) {
                    vis[v] = 1;
                    que[++tail] = v;
                }
            }
        }
    }
}

int astar(int s, int t) {
    memset(vis, 0, sizeof(vis));
    memset(g, 0x3f, sizeof(g));
    memset(f, 0x3f, sizeof(f));
    g[s] = 0, f[s] = h[s];
    int ans = INT_MAX;
    top = tail = 0;
    que[++tail] = s;
    while (top < tail) {
        int u = que[++top];
        if (g[u] + h[u] >= ans) continue;
        if (u == t) {
            ans = min(ans, g[u] + h[u]);
            continue;
        }
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            if (vis[v]) continue;
            if (g[v] > g[u] + w) {
                g[v] = g[u] + w;
                f[v] = g[v] + h[v];
                que[++tail] = v;
            }
        }
        sort(que + top + 1, que + tail + 1, [](int u, int v) {
            return f[u] > f[v];
        });
    }
    return ans;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    scanf("%d", &h[t]);
    spfa(s, dis, g);
    int ans = astar(s, t);
    memset(vis, 0, sizeof(vis));
    spfa(t, dis, g);
    for (int i = 1; i <= n; ++i) {
        for (int j = head[i]; j; j = e[j].nxt) {
            int u = i, v = e[j].to, w = e[j].w;
            if (g[u] + w + h[v] == ans) {
                e[j].w = 0;
                add(v, u, 0);
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    printf("%d\n", astar(s, t));
    return 0;
}

其中，`add(u, v, w)` 函数用于向邻接表中添加一条从节点 `u` 到节点 `v`，权值为 `w` 的边。

`spfa(s, dis, h)` 函数用于从节点 `s` 开始进行一次SPFA算法，最终将每个节点到节点 `s` 的最短距离存储在 `dis` 数组中，将每个节点到目标节点 `t` 的估价函数值存储在 `h` 数组中。

`astar(s, t)` 函数用于进行一次A*搜索，返回从节点 `s` 到节点 `t` 的最短路长度。在搜索过程中，我们使用 `g` 数组存储从节点 `s` 到当前节点的距离，使用 `h` 数组存储当前节点到目标节点 `t` 的估价函数值，使用 `f` 数组存储当前节点的估价函数值。我们使用一个优先队列来维护搜索顺序。

在主函数中，我们首先使用 `spfa(s, dis, g)` 计算出正向图的最短路长度和每个节点到目标节点的估价函数值，然后使用 `astar(s, t)` 进行双向A*搜索，将每条满足条件的边的权值设置为0，再将这些边添加到反向图中，最后使用 `astar(s, t)` 计算出反向图的最短路长度，即为双向A*搜索的结果。

需要注意的是，在进行反向图的SPFA算法时，需要将 `dis` 数组和 `g` 数组重新初始化为正无穷值，因为这些数组在正向图的SPFA算法和A*搜索中被修改过了。