A*解决 K 短路

定义

定义估价函数 \(f=g+h\)

\(f(x)\) 为总估价值

\(g(x)\) 为真实价值

\(h(x)\) 为当前估价值

对于 \(K\) 短路问题来说 \(f\) 为 \(s \to t\) 的总花费，\(g\) 为 \(s \to x\) 的真实花费，\(h\) 为 \(x \to t\) 的预估花费

过程

\(h(x)\) 的存在要求在以 \(t\) 为起点的反向图中求出最短路

初始状态放入优先队列中

每次依次挑 \(f\) 最小的节点，对邻接的点重新估值更新并加入队列中

当第 \(k\) 此到达节点 \(t\)，就是 \(s \to t\) 的 \(K\) 短路

优化部分：对于某个经过 \(k+1\) 次的节点肯定不会是 \(K\) 短路，直接剪枝

完成版

#include<bits/stdc++.h>
using namespace std;
 
namespace util {
    inline void fast_io() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
}
 
struct Edge {
    int to;
    double cost;
};
 
using VE = vector<Edge>;
inline void add(vector<VE> &e,int from,int to,double cost) {
    e[from].push_back({to,cost});
}
 
using P = pair<double,int>;
void dijkstra(vector<VE> &edges,vector<double> &dis,int s) {
    dis[s] = 0;
    priority_queue<P,vector<P>,greater<P>> que;
    que.push({0,s});
    while(!que.empty()) {
        P p = que.top(); 
        que.pop();
        int u = p.second;
        if(dis[u] < p.first) continue;
        for(auto &edge : edges[u]) {
            auto v = edge.to;
            auto w = edge.cost;
            if(dis[v] > dis[u]+w) {
                dis[v] = dis[u]+w;
                que.push({dis[v],v});
            }
        }
    }
}
 
 
int a_star(vector<int> &cnt,vector<double> &h,
           vector<VE> &edges,int eng,int k,int s,int t) {
    int ans = 0;
    auto fx = [&](const P &a,const P &b) {
        return a.first+h[a.second] > b.first+h[b.second]; // g(x)+h(x) 
    };
    priority_queue<P,vector<P>,decltype(fx)> que(fx);
    que.push({0,s});
    while(!que.empty()) {
        P p = que.top();
        que.pop();
        auto u = p.second;
        auto gu = p.first; // first 存放 g(x) 
        cnt[u]++;
        if(u == t) {
            eng -= p.first;
            if(eng < 0) return ans;
            ans++;
        }
        if(cnt[u] > k) continue;
        for(auto &edge : edges[u]) {
            auto v = edge.to;
            auto w = edge.cost;
            if(eng < gu+w+h[v]) continue; // gv = gu+w
            que.push({gu+w,v});
        }
    }
    return ans;
}
 
int main() {
    util::fast_io(); 
    int n,m;
    double eng;
    cin >> n >> m >> eng;
    vector<VE> e1(n+1),e2(n+1);
    for(int i = 0; i < m; i++) {
        int u,v;
        double w;
        cin >> u >> v >> w;
        add(e1,u,v,w);
        add(e2,v,u,w);
    }
    vector<double> h(n+1,0x3f3f3f3f);
    dijkstra(e2,h,n);
    vector<int> cnt(n+1);
    int k = (int)eng/h[1];
    cout << a_star(cnt,h,e1,eng,k,1,n) << endl;
    return 0;
}
/*
4 6 14.9
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5

3
*/