题意
给出一个 \(n\) 个点 \(m\) 条边的正权有向图,求从点 \(n\) 到点 \(1\) 的前 \(k\) 短路的距离分别是多少。
sol
\(k\) 短路问题往往使用 A* 算法(时间复杂度 \(O(nk\log n)\))或可持久化可并堆优化最短路树(时间复杂度 \(O((n+m) \log m + k \log k)\)),由于本题数据范围较小,可以使用更好写的 A* 算法。
A* 算法
A* 算法是启发式搜索的一种,其核心是估价函数 \(f(x)=g(x) + h(x)\),其中,\(g(x)\) 是当前到达状态 \(x\) 的最小代价,\(h(x)\) 是状态 \(x\) 到达目标状态的估计最小代价(该值必须不大于实际代价,且越大越好)。每次选择 \(f(x)\) 最小的未选择的状态,直到到达目标状态
\(k\) 短路
对于本题,我们计 \(h(x) = dist(x,1)\),这样可以保证一定不大于第 \(k\) 短路中这一段的距离。然后执行 A* 算法,当点 \(1\) 被遍历 \(k\) 次后,返回即可。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIP;
const int N = 1005, M = 10005;
struct Graph{
int h[N], e[M], w[M], ne[M], idx;
Graph(){
memset(h, -1, sizeof h);
}
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
} G, Ginv;
int n, m, k;
int h[N];
bool st[N];
int cnt[N];
void dijkstra(){
memset(h, 0x3f, sizeof h);
h[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});
while (!heap.empty()){
PII t = heap.top();
heap.pop();
if (st[t.y]) continue;
st[t.y] = true;
for (int i = Ginv.h[t.y]; ~i; i = Ginv.ne[i]){
int j = Ginv.e[i];
if (h[j] > h[t.y] + Ginv.w[i]) {
h[j] = h[t.y] + Ginv.w[i];
heap.push({h[j], j});
}
}
}
}
void A_star(){
priority_queue<PIP, vector<PIP>, greater<PIP>> heap;
heap.push({h[n], {0, n}});
while (!heap.empty()){
PIP t = heap.top();
heap.pop();
cnt[t.y.y] ++ ;
if (t.y.y == 1) {
printf("%d\n", t.x);
if (cnt[t.y.y] == k) return ;
}
for (int i = G.h[t.y.y]; ~i; i = G.ne[i]) {
int j = G.e[i];
if (cnt[j] > k) continue;
heap.push({t.y.x + G.w[i] + h[j], {t.y.x + G.w[i], j}});
}
}
}
int main(){
scanf("%d%d%d", &n, &m, &k);
while (m -- ){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
G.add(a, b, c), Ginv.add(b, a, c);
}
dijkstra();
A_star();
for (int i = cnt[1]; i < k; i ++ ) puts("-1");
return 0;
}
标签:luoguP2901,cnt,idx,Cow,int,Jogging,heap,include,Ginv
From: https://www.cnblogs.com/XiaoJuRuoUP/p/-/luoguP2901