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; }