A* AcWing 178. 第K短路

淩亂°似流年 2024-04-07 10:09 59阅读 0赞

## A\* AcWing 178. 第K短路 ##

### 原题链接 ###

[AcWing 178. 第K短路][AcWing 178. _K]

### 算法标签 ###

搜索 A\* dijkstra 最短路

### 思路 ###

##### A\* 应用场景: #####

起点→终点的最短距离  
状态空间 >> 1e10  
启发函数减小搜索空间

##### A\*算法步骤: #####

while(q.size())
        t ← 优先队列的队头  小根堆
            当终点第一次出队时 break;
            从起点到当前点的真实距离 d_real
            从当前点到终点的估计距离 d_estimate
            选择一个估计距离最小的点 min(d_estimate)
        for j in ne[t]:
            将邻边入队

##### A\*算法条件: #####

估计距离<=真实距离  
d\[state\] + f\[state\] = 起点到state的真实距离 + state到终点的估计距离=估计距离  
^  
d\[state\] + g\[state\] = 起点到state的真实距离 + state到终点的真实距离=真实距离  
一定是有解才有 d\[i\]>= d\[最优\] = d\[u\]+f\[u\](f\[u\] >= 0)

##### 证明 #####

证明终点第一次出队列即最优解  
1 假设终点第一次出队列时不是最优  
则说明当前队列中存在点u  
有 d\[估计\]< d\[真实\]  
d\[u\] + f\[u\] <= d\[u\] + g\[u\] = d\[队头终点\]  
即队列中存在比d\[终点\]小的值,  
2 但我们维护的是一个小根堆,没有比d\[队头终点\]小的d\[u\],矛盾  
证毕  
A\* 不用判重  
以边权都为1为例  
A o→o→o  
↑ ↓  
S o→o→o→o→o→o→o T  
B  
dist\[A\] = dist\[S\]+1 + f\[A\] = 7  
dist\[B\] = dist\[S\]+1 + f\[B\] = 5  
则会优先从B这条路走到T  
B走到T后再从A这条路走到T

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    #define x first
    #define y second
    using namespace std;
    typedef pair<int, int> PII;
    typedef pair<int, PII> PIII;
    const int N=1005, M=200010;
    int n, m, S, T, K;
    // h正向邻接表表头 rh反向邻接表表头 w存储边值权值 ne存储下一个节点 
    int h[N], rh[N], e[M], w[M], ne[M], idx;
    // cnt[i]=j 存储终点为i的点第j短路
    int d[N],cnt[N]; 
    bool st[N];
    inline int rd(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void add(int h[], int a, int b, int c){
        e[idx]=b, w[idx]=c, ne[idx]=h[a], h[a]=idx++; 
    }
    void dij(){
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        heap.push({0, T});
        memset(d, 0x3f, sizeof d);
        d[T]=0;
        while(heap.size()){
            PII t=heap.top();
            heap.pop();
            if(st[t.y]){
                continue;
            }else{
                st[t.y]=true;
            } 
            // 建反向边dijkstra求各点到终点的距离作为估计值f[u]， 因此采用反向搜索
            for(int i=rh[t.y]; ~i; i=ne[i]){
                int j=e[i];
                if(d[j]>d[t.y]+w[i]){
                    d[j]=d[t.y]+w[i];
                    heap.push({d[j], j});
                }
            }
        }
    }
    int astar(){
        priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
        // 将最小的d[u]+f[u]出队列
        heap.push({d[S], {0, S}});
        while(heap.size()){
            PIII t=heap.top();
            heap.pop();
            int v=t.y.y, dis=t.y.x;
            cnt[v]++;
            //如果终点已经被访问过k次了 则此时的ver就是终点T 返回答案
            if(cnt[T]==K){
                return dis;
            }
            for(int i=h[v]; ~i; i=ne[i]){
                int j=e[i];
                /* 
                如果走到中间点时cnt[j]>=K，说明j已经出队k次了，且astar()并没有return distance,
                说明从j出发找不到第k短路(让终点出队k次)，
                即继续让j入队的话依然无解，
                那么就没必要让j继续入队了
                */
                if(cnt[j]<K){
                    // 按 真实值+估计值 = d[j]+f[j] = dist[S->t] + w[t->j] + dist[j->T] 堆排
                    // 真实值 dist[S->t] = distance+w[i]heap.push({dis+w[i]+d[j], {dis+w[i], j}});
                     heap.push({dis+w[i]+d[j], {dis+w[i], j}});
                }
            }
        }
        // 终点没有被访问k次
        return -1;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        n=rd(), m=rd();
        memset(h, -1, sizeof h);
        memset(rh, -1, sizeof rh);
        while(m--){
            int a=rd(), b=rd(), c=rd();
            add(h, a, b, c), add(rh, b, a, c);
        }
        S=rd(), T=rd(), K=rd();
        if(S==T){
            K++;
        }
        dij();
        printf("%lld\n", astar());
        return 0;
    }

参考文献  
[AcWing 178. 第K短路(A\* 反向计算最短路作为到终点的估计值) ][AcWing 178. _K_A_ _]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 178. _K]: https://www.acwing.com/problem/content/180/
[AcWing 178. _K_A_ _]: https://www.acwing.com/solution/content/21233/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/070bd2a583c241d0b08c5381f30b0e02.png