ACWING 178. 第K短路（A*算法）

本文主要是介绍ACWING 178. 第K短路（A*算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：
$k$短路模板题。
引入估值函数$d(x)$代表从$x$出发到终点的最短距离，这可以通过反向最短路求出来。维护$f(x)$代表起点出发到$x$点的最短距离。
$A\ast$算法中堆中每次取出最小的$f(x)+d(x)$对应的点进行松弛。这样一个点第$k$次出堆得到的就是第$k$短路。

#include <iostream>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <vector>using namespace std;typedef pair<int,int>PII;
typedef pair<int,PII>PIII;
const int maxn = 1e3 + 7;
vector<PII>G[maxn],rG[maxn];
priority_queue<PIII,vector<PIII>,greater<PIII>>heap;
priority_queue<PII,vector<PII>,greater<PII>>q;
int cnt[maxn],dis[maxn],vis[maxn];
int S,T,K;
void dij() {q.push({0,T});memset(dis,0x3f,sizeof(dis));dis[T] = 0;while(!q.empty()) {int u = q.top().second;q.pop();if(vis[u]) continue;vis[u] = 1;for(int i = 0;i < rG[u].size();i++) {int v = rG[u][i].first,w = rG[u][i].second;if(dis[v] > dis[u] + w) {dis[v] = dis[u] + w;q.push({dis[v],v});}}}
}
int Astar() {heap.push({dis[S],{0,S}});while(!heap.empty()) {auto t = heap.top();heap.pop();int u = t.second.second,distance = t.second.first;cnt[u]++;if(cnt[T] == K) return distance;for(int i = 0;i < G[u].size();i++) {int v = G[u][i].first,w = G[u][i].second;if(cnt[v] < K) {heap.push({distance + w + dis[v],{distance + w,v}});}}}return -1;
}
int main() {int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= m;i++) {int x,y,z;scanf("%d%d%d",&x,&y,&z);G[x].push_back({y,z});rG[y].push_back({x,z});}scanf("%d%d%d",&S,&T,&K);if(S == T) K++;dij();printf("%d\n",Astar());return 0;
}

这篇关于ACWING 178. 第K短路（A*算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---