A*算法学习笔记

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1020;
int dis[MAXN];
struct Node {
    int v, w;
    Node(int v, int w) : v(v), w(w) {}
    Node() {}
    /*这里是对估价函数的使用，使得路径最短的先出队（小根堆）*/
    inline bool operator < (const Node &a) const {
        return w + dis[v] > a.w + dis[a.v];
    }
};
/*-----------正图--------反图-----*/
vector<Node> edge[MAXN], rev[MAXN];
/*求所有点到终点（t）的最短路径(即反向求t到各点的最短路)*/
/**dijkstra
 *@param s 反向图起点，即要求的第k短路的终点
 *@param n 点数
 */
inline void dijkstra(int s, int n) {
    fill(dis + 1, dis + n + 1, INT_MAX);
    static bool vis[MAXN];
    memset(vis, 0, sizeof(vis));
    priority_queue<Node> q;
    dis[s] = 0;
    q.push(Node(s, dis[s]));
    while (!q.empty()) {
        register int now = q.top().v;
        q.pop();
        if (vis[now]) continue;
        vis[now] = true;
        /*注意这里是枚举反向图，其他同普通dijkstra*/
        for (register int i = 0; i < rev[now].size(); i++) {
            Node *x = &rev[now][i];
            if (dis[now] + x->w < dis[x->v])
                dis[x->v] = dis[now] + x->w, q.push(Node(x->v, dis[x->v]));
        }
    }
}
/**A*搜索
 *@param s 起点
 *@param t 终点
 *@param k 求的第k短路
 *@param n 点数
 */
inline int AStar(int s, int t, int k, int n) {
    if (dis[s] == INT_MAX) return -1;/*终点t到起点s不通，则返回-1*/
    priority_queue<Node> q;/*定义了一个优先队列（小根堆）*/
    static int cnt[MAXN];/*cnt[i]存储第i条边第几次出队*/
    memset(cnt, 0, sizeof(cnt));
    q.push(Node(s, 0));
    while (!q.empty()) {/*如果队列不空 ，循环*/
        const Node now = q.top();/*与起点距离最短的点出队*/
        q.pop();/*删除队首*/
        cnt[now.v]++;/*记录u出队次数*/
        if (cnt[t] == k) return now.w;/*如果终点第k次出队，则找到"s到t的第k短路"*/
        /*出队超过k次, 说明已经把前k短路都用于更新其它点了,
         *而一个点的前k短路只可能由其它点的前k短路更新而来,
         * 所以点u的第k+1短路已经失去了更新其它点的意义, 
         *可以直接出队*/
        if (cnt[now.v] > k) continue;
        /*枚举所有从u出发的正向边i*/
        for (register int i = 0; i < edge[now.v].size(); i++)
            q.push(Node(edge[now.v][i].v, now.w + edge[now.v][i].w));
        /*把边u~v加入优先队列，自动按到起点的距离形成小根堆*/
    }
    return -1;
}
/**
 *@param s 起点
 *@param t 终点
 *@param k 求的第k短路
 *@param n 点数
 */
inline int getKthDis(int s, int t, int k, int n) {
    /*如果 s==t ，那么就是求 k+1 短路*/
    if (s == t) k++;
    dijkstra(t, n);
    return AStar(s, t, k, n);
}
inline void addEdge(int u, int v, int w) {
    edge[u].push_back(Node(v, w));
    /*建反图*/
    rev[v].push_back(Node(u, w));
}
int main() {
    int n, m, s, t, k;
    while (~scanf("%d %d", &n, &m)) {
        for (register int i = 0, u, v, w; i < m; i++)
            scanf("%d %d %d", &u, &v, &w), addEdge(u, v, w);
        scanf("%d %d %d", &s, &t, &k);
        printf("%d\n", getKthDis(s, t, k, n));
    }
    return 0;
}

#include <queue>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct Knight {
    int x, y, step;
    int g, h, f;
    /*启发式函数*/
    inline bool operator < (const Knight &b) const {
        return f > b.f;
    }
} k;
/*已访问标记(关闭列表)*/
bool vis[8][8];
/*起点(x1,y1),终点(x2,y2),最少移动次数ans*/
int x1, x2, y1, y2, ans;
/*8个移动方向*/
int dirs[8][2] = {
    {-2, -1}, {-2, 1}, {2, -1}, {2, 1}, 
    {-1, -2}, {-1, 2}, {1, -2}, {1, 2}
};
/*最小优先级队列(开启列表)*/
priority_queue<Knight> que;
/*判断是否在棋盘内*/
inline bool check(const Knight &a) {
    if (a.x < 0 || a.y < 0 || a.x >= 8 || a.y >= 8)
        return false;
    return true;
}
inline int abs(int a) {
    return a < 0 ? -a : a;
} 
/*manhattan距离估价函数*/
inline int heuristic(const Knight &a) {
    return (abs(a.x - x2) + abs(a.y - y2)) * 10;
}
inline void AStar() {
    Knight t, s;
    while (!que.empty()) {
        t = que.top(), que.pop(), vis[t.x][t.y] = true;
        if (t.x == x2 && t.y == y2) {
            ans = t.step;
            break;
        }
        for (int i = 0; i < 8; i++) {
            s.x = t.x + dirs[i][0], s.y = t.y + dirs[i][1];
            if (check(s) && !vis[s.x][s.y]) {
                /*23 = Math.ceil(Math.sqrt(5) * 10)*/
                s.g = t.g + 23;
                s.h = heuristic(s);
                s.f = s.g + s.h;
                s.step = t.step + 1;
                que.push(s);
            }
        }
    }
}
int main() {
    char line[5];
    while (cin.getline(line, 6)) {
        x1 = line[0] - 'a', y1 = line[1] - '1', x2 = line[3] - 'a', y2 = line[4] - '1';
        memset(vis, 0, sizeof(vis));
        k.x = x1, k.y = y1, k.g = k.step = 0, k.h = heuristic(k), k.f = k.g + k.h;
        while (!que.empty()) que.pop();
        que.push(k);
        AStar();
        printf("To get from %c%c to %c%c takes %d knight moves.\n", line[0], line[1], line[3], line[4], ans);
    }
    return 0;
}