是什么
字面意思
一种用于求解有向图上从某一起点到某一终点的所有可行路径中第 \(k\) 小（大）的算法。
怎么做
首先把模板放在 这里
其实我并不知道还有没有其他应用
A*
注：对于 \(k\) 短路问题，A* 算法的最坏时间复杂度是 \(O(nk \log n)\) 的。虽然 A* 算法可以通过本题原版数据，但可以构造数据，使得 A* 算法在原题的数据范围内无法通过。事实上，存在使用可持久化可并堆的算法可以做到在 \(O((n+m) \log n + k \log k)\) 的时间复杂度解决 \(k\) 短路问题。详情见 OI-Wiki。
（摘自 Luogu k短路 模板题的题目背景）
想要直接学 可持久化可并堆 做法的可以跳过这里。
虽然时间复杂度假了，但是依然可以作为 A* 算法的一个入门练习。
这里放一个可以使用 A* 通过的模板题 链接
具体做法
什么，你连 Dijkstra 都不会？那快去学你的入门课（
或者看看 我的？
我们在使用 Dijkstra 的堆优版本求解 最短路 问题时，是这样写的：（这里只写了关键代码）
struct node{
int to,dis;
friend bool operator < (node n1,node n2){
return n1.dis>n2.dis;
}
};
void dij(int s){
for(int i=1;i<=n;i++) dis[i]=inf;
dis[s]=0;
priority_queue<node> q;
q.push((node){s,0});
while(!q.empty()){
int u=q.top().to;
q.pop();
if(sure[u]) continue;
sure[u]=true;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(sure[v]) continue;
if(dis[v]>dis[u]+edge[i].val){
dis[v]=dis[u]+edge[i].val;
q.push((node){v,dis[v]});
}
}
}
}我们可以看出，在 Dijkstra 中，每个点最多只会用于一次松弛操作
可持久化可并堆
正解！
可以去看 俞鼎力大牛的课件，其实讲解还是很详细的（？），至少我是从这个原课件看懂的（
那么首先，你至少得会 可并堆（左偏树）
不然从何谈起（
不会也没事，点击链接可以跳转到学习地址（
ps：上面放的是我未来会写的内容
（咕咕咕），在这条 ps 还在的时候，你可以看 这个