A*算法求第k短路
话不多说先上例题。。
acwing：178. 第K短路
给定一张 NN 个点（编号 1,2…N1,2…N），MM 条边的有向图，求从起点 SS 到终点 TT 的第 KK 短路的长度，路径允许重复经过点或边。
注意： 每条最短路中至少要包含一条边。
输入格式
第一行包含两个整数 NN 和 MM。
接下来 MM 行，每行包含三个整数 A,BA,B 和 LL，表示点 AA 与点 BB 之间存在有向边，且边长为 LL。
最后一行包含三个整数 S,TS,T 和 KK，分别表示起点 SS，终点 TT 和第 KK 短路。
输出格式
输出占一行，包含一个整数，表示第 KK 短路的长度，如果第 KK 短路不存在，则输出 −1−1。
数据范围
1≤S,T≤N≤10001≤S,T≤N≤1000,
0≤M≤1040≤M≤104,
1≤K≤10001≤K≤1000,
1≤L≤1001≤L≤100输入样例：
2 2 1 2 5 2 1 4 1 2 2输出样例：
14
思路：
整体思路就是先逆向求一次dijkstral，将各点到目标点的最短路求出来，以此作为A*的估计值。然后在采用A*求第K短路，当第K次目标点出队列是，返回值即可。注意起点终点一直时需要将k+1，将原地不动的情况除去。
上代码：
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; typedef pair<int,PII> PIII; #define y second #define x first const int N=1010,M=3e4+10; int s, t ,k; int n,m; int h[N],h2[N],e[M],ne[M],w[M],idx; int dis[N],cnt[N]; bool st[N]; void add(int h[],int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void dijkstral(){memset(dis,0x3f,sizeof(dis));priority_queue<PII,vector<PII>,greater<PII>>q;dis[t]=0;q.push({0,t});while(q.size()){auto T=q.top();q.pop();int u=T.y;if(st[u]){continue;}st[u]=true;for(int i=h2[u];~i;i=ne[i]){int j=e[i];if(st[j]){continue;}if(dis[j]>dis[u]+w[i]){dis[j]=dis[u]+w[i];q.push({dis[j],j});}}} } int astar(){priority_queue<PIII,vector<PIII>,greater<PIII>> q;q.push({dis[s],{0,s}});while(q.size()){auto T=q.top();q.pop();int dist=T.y.x;int u=T.y.y;cnt[u]++;if(cnt[t]==k){return dist;}for(int i=h[u];~i;i=ne[i]){int j=e[i];if(cnt[j]>k){continue;}q.push({dist+w[i]+dis[j],{dist+w[i],j}});}}return -1; } int main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(h,-1,sizeof(h));memset(h2,-1,sizeof(h2));cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;add(h,a,b,c);add(h2,b,a,c);}cin>>s>>t>>k;dijkstral();if(s==t){k++;}int ans=astar();cout<<ans; }
这里附上一道例题，求次短路。。
算是A*的特殊情况了，去直接秒杀吧。
acwing：133. 第二短路
贝茜把家搬到了一个小农场，但她常常回到 FJ 的农场去拜访她的朋友。
贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不像我们所习惯的那样，选择最短路。
贝茜所在的乡村有 RR 条双向道路，每条路都连接了所有的 NN 个农场中的某两个。
贝茜居住在农场 11，她的朋友们居住在农场 NN（即贝茜每次旅行的目的地）。
贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且一条路可以重复走多次。
当然第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。
输入格式
第一行包含两个整数 NN 和 RR。
接下来 RR 行，每行包含三个整数 A,B,DA,B,D，表示农场 AA 和农场 BB 之间存在一条长度为 DD 的路。
输出格式
输出仅包含一个整数，表示从农场 11 到农场 NN 的第二短路的长度。
数据范围
1≤R≤1051≤R≤105,
1≤N≤50001≤N≤5000,
1≤D≤50001≤D≤5000,
1≤A,B≤N1≤A,B≤N输入样例：
4 4 1 2 100 2 4 200 2 3 250 3 4 100输出样例：
450
#include<bits/stdc++.h> using namespace std; const int N=5010,M=4e5+10; #define x first #define y second typedef pair<int,int>PII; typedef pair<int,PII>PIII; int h[N],e[M],ne[M],w[M],idx; int dis[N]; bool st[N]; int cnt[N]; int n,m;void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void dijkstral() {memset(dis,0x3f,sizeof(dis));priority_queue<PII,vector<PII>,greater<PII>>q;q.push({0,n});dis[n]=0;while(q.size()){auto t=q.top();q.pop();int v=t.y;if(st[v]){continue;}st[v]=true;for(int i=h[v];~i;i=ne[i]){int j=e[i];if(st[j]){continue;}if(dis[j]>dis[v]+w[i]){dis[j]=dis[v]+w[i];q.push({dis[j],j});}}} } int astar(){int flag=0;priority_queue<PIII,vector<PIII>,greater<PIII>>q;q.push({dis[1],{0,1}});while(q.size()){auto t=q.top();q.pop();int v=t.y.y;int dist=t.y.x;cnt[v]++;if(cnt[n]==1){flag=dist;}if(cnt[n]>=2&&dist>flag){return dist;}for(int i=h[v];~i;i=ne[i]){int j=e[i];if(cnt[j]>2){continue;}q.push({dist+dis[j]+w[i],{dist+w[i],j}});}} } int main() {ios::sync_with_stdio(0);cout.tie(0),cin.tie(0);memset(h,-1,sizeof(h));cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);add(b,a,c);}dijkstral();int ans=astar();cout<<ans; }