思路分析

A*算法模板

int a_star(){
    memset(st, 0, sizeof st);
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> heap;//注意代价和实际距离要维护在一起，否则会出错
    heap.push({0+f[start], {0, start}});
    while(heap.size()){
        auto t = heap.top();heap.pop();
        int x = t.first, y = t.second.second, z = t.second.first;
        ++st[y];
        if(y == ed && st[y] == k) return z;
        if(st[y] >= k) continue;
        for(int i = h[y];~i;i = ne[i]){
            int j = v[i];
            heap.push({z + w[i] + f[j], {w[i] + z, j}});
        }
    }
    return -1;
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int N = 1010, M = 2*1e5+10;

int h[N], rh[N], w[M], ne[M], v[M], idx;
int f[N], dist[N], st[N];
int n, m;
int start, ed, k;

void add(int* h, int a, int b, int c){
    ++idx;v[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx;
}

void dijkstra(){
    memset(f, 0x3f, sizeof f);
    priority_queue<pii, vector<pii>, greater<pii> > heap;   
    heap.push({0, ed});
    f[ed] = 0;
    while(heap.size()){
        auto t = heap.top();heap.pop();
        if(st[t.second]) continue;
        st[t.second] = 1;
        for(int i = rh[t.second];~i;i = ne[i]){
            int j = v[i];
            if(f[j] > f[t.second] + w[i]){
                f[j] = f[t.second] + w[i];
                heap.push({f[j], j});
            }
        }
    }
}

int a_star(){
    memset(st, 0, sizeof st);
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> heap;
    heap.push({0+f[start], {0, start}});
    while(heap.size()){
        auto t = heap.top();heap.pop();
        int x = t.first, y = t.second.second, z = t.second.first;
        ++st[y];
        if(y == ed && st[y] == k) return z;
        if(st[y] >= k) continue;
        for(int i = h[y];~i;i = ne[i]){
            int j = v[i];
            heap.push({z + w[i] + f[j], {w[i] + z, j}});
        }
    }
    return -1;
}

int main(){
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    cin >> n >> m;
    for(int i = 0;i < m;++i){
        int a, b, c;cin >> a >> b >> c;
        add(h, a, b, c);        
        add(rh, b, a, c);
    }
    cin >> start >> ed >> k;
    if(start == ed) ++k;
    dijkstra();
    cout << a_star() << endl;
    return 0;
}