AcWing 178 第K短路

题目传送门
A星算法详解(个人认为最详细,最通俗易懂的一个版本)
二、代码实现

#include 

using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair PII;
typedef pair PIII;
#define x first
#define y second

const int N = 1010, M = 200010; //因为要建反向边，所以边数是2倍，20W+10
int n, m;                       //点数和边数
int S, T, K;                    //起点，终点，第K短
int h[N], rh[N];                //正向边的邻接表表头和反向边的邻接表表头
int e[M], w[M], ne[M], idx;     //数组模拟邻接表
int dist[N];                    //到每个点的最短距离
bool st[N];                     //每个点用没用过
int cnt[N];

//邻接表模板
void add(int h[], int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

// 堆优化版本的dijkstra
// 通过这个反向搜索的dijkstra,就可以计算出点T到每个其它点的最短距离,把这个最短距离dist[i]做为估价函数
void dijkstra() {
    priority_queue, greater> heap; // 优先队列，小根堆

    //小根堆是要求按到起点的距离进行由小到大自动排序的，现在反向搜索，当然距离是T的距离是0
    heap.push({0, T}); // 终点T是这里的起点 <距离，点编号>,小根堆，默认按PII的first进行排序，
    //即距离起点的长度由小到大排序

    //初始化距离
    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;

    while (heap.size()) {
        PII t = heap.top();
        heap.pop();

        int u = t.y;                         //要处理哪个点
        if (st[u]) continue;                 //如果这个点已经出过队列了
        st[u] = true;                        //标识已搜索
        for (int i = rh[u]; ~i; i = ne[i]) { //在反向图上遍历，rh[]数组
            int j = e[i];                    //点u有一条到点j的边
            if (dist[j] > dist[u] + w[i]) {  //如果能通过点u优化掉到点j的距离，就优化一下
                dist[j] = dist[u] + w[i];
                heap.push({dist[j], j}); //并且将点j和点距离出发点T的距离组成数对放入到优化队列中
            }
        }
    }
}

// A*算法
// A* 不用判重
int astar() {
    //小顶堆，对F值进行从小到大排序，每次取队首
    priority_queue, greater> heap;
    // 小顶堆内的元素：
    // PII的first: F = G + H
    // G = 从起点 A 移动到指定方格的移动代价，沿着到达该方格而生成的路径。
    // H = 从指定的方格移动到终点 B 的估算成本。
    // 在A*中，用来使用小顶堆排序的，其实是这个F，也就是实际距离累加和+估算值,按这个值来确定处理优先级
    heap.push({dist[S], {0, S}}); //在添加S节点时，由于S距离自己的距离是0，所以就可有一个H值，即dist[S]
    //后面数对PII的含义是：当前节点距离出发点的距离，当前节点号

    while (heap.size()) {
        PIII t = heap.top();
        heap.pop();
        // t.x在下面的代码中未使用，原因很简单，这个x本来也不是啥准确值，只是一个估值
        int distance = t.y.x; // u距离出发点的叠加距离
        int u = t.y.y;        // 下一个要扩展的点u
        cnt[u]++;             // 点u出队的次数++

        //如果此时的u就是终点T,前且已经出队k次 返回答案
        if (u == T && cnt[u] == K) return distance;

        for (int i = h[u]; ~i; i = ne[i]) { //枚举与u相连的所有出边
            int j = e[i];                   //找到节点j
            /*
            A*寻路的一个优化:
            如果走到一个中间点都cnt[j]>=K，则说明j已经出队k次了，且astar()并没有return distance,
            说明从j出发找不到第k短路(让终点出队k次),即继续让j入队的话依然无解，那么就没必要让j继续入队了
            */
            if (cnt[j] < K) {
                // distance + w[i] 累加长度
                // 真实值+估计值 排序
                heap.push({distance + w[i] + dist[j], {distance + w[i], j}});
            }
        }
    }
    // 终点没有被访问k次
    return -1;
}

int main() {
    cin >> n >> m;

    memset(h, -1, sizeof h);   //正向边表头
    memset(rh, -1, sizeof rh); //反向边表头

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(h, a, b, c);  //建正边
        add(rh, b, a, c); //建反边
    }

    cin >> S >> T >> K;
    if (S == T) K++; //最短路中至少要包含一条边，如果S和T相等，那么我们不能直接从S得到T，所以起码需要走一条边，
    //所以求第K+1短就可以了

    //先执行一遍dijkstra算法，求出终点到每个点的最短距离，作为估值
    dijkstra();

    // A*寻路求第K短长度
    printf("%d\n", astar());

    return 0;
}
AcWing提高课搜索-A寻路
AcWing 178 第K短路

二、代码实现

相关

标签
