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