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