A* & IDA*搜尋

$f(n)=g(n)+h(n)$
不但考慮前向代價，而且考慮後向代價。由於後向代價不可知，因而需要使用估價函數。

題目

HDU 6181
求次短路，先反向SPFA準確求出$h(n)$準確的後向代價，再用A*搜尋，第幾次去到終點就是第幾短路。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=1e5+10;
struct Edge{
    int to;
    ll len;
    Edge(int a=0,ll b=0ll):to(a),len(b) {}
    bool operator< (const Edge& e) const {
        return len > e.len;
    }
};
struct Path{
    int u;
    ll g,h;
    Path(int a,ll b,ll c):u(a),g(b),h(c) {}
    bool operator< (const Path& p) const {
        return g+h > p.g+p.h;
    }
};
struct E{
    int to,next;
    ll len;
}e[2*maxn];
int n,m,head[maxn];
ll h[maxn];
bool vis[maxn];int cnt=0;
void add(int v,int u,ll len){
    e[cnt]={u,head[v],len};
    head[v]=cnt++;
    e[cnt]={v,head[u],len};
    head[u]=cnt++;
}
void spfa(){
    queue<int> Q;
    Q.emplace(n);
    memset(vis,0,sizeof vis);
    memset(h,0x7f,sizeof h);
    h[n]=0;
    while(!Q.empty()){
        int now=Q.front();
        Q.pop();vis[now]=false;
        for(int i=head[now];~i;i=e[i].next){
            if(e[i].len+h[now]>h[e[i].to])continue;
            h[e[i].to]=e[i].len+h[now];
            if(vis[e[i].to])continue;
            vis[e[i].to]=true;
            Q.emplace(e[i].to);
        }
    }
}
ll Astar(){
    priority_queue<Path> Q;
    Q.emplace(1,0,h[1]);
    int cnt=0;
    while(!Q.empty()){
        Path now=Q.top();
        Q.pop();
        if(now.u==n && ++cnt==2)return now.g+now.h;  //次短路爲2，若k短路改爲++cnt==k
        for(int i=head[now.u];~i;i=e[i].next){
            ll before=now.g+e[i].len,after=h[e[i].to];
            Q.emplace(e[i].to,before,after);
        }
    }
    return 0;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        int u,v;
        for(int i=1;i<=n;++i)
            head[i]=-1;
        cnt=0;
        ll len;
        while(m--){
            cin>>u>>v>>len;
            add(u,v,len);
        }
        spfa();
        cout<<Astar()<<endl;
    }
}