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
*/

发表评论

电子邮件地址不会被公开。 必填项已用*标注