第K短路(A*算法）

给定一张 N个点（编号 1,2…N），M条边的有向图，求从起点 S到终点 T 的第 K 短路的长度，路径允许重复经过点或边。

注意： 每条最短路中至少要包含一条边。

输入格式

第一行包含两个整数 N 和 M。

接下来 M 行，每行包含三个整数 A,B, 和 L，表示点 A 与点 B 之间存在有向边，且边长为 L。

最后一行包含三个整数 S,T 和 K，分别表示起点 S，终点 T 和第 K 短路。

输出格式

输出占一行，包含一个整数，表示第 K 短路的长度，如果第 K 短路不存在，则输出 −1−1。

数据范围

1≤S,T≤N≤1000,
0≤M≤10^4,
1≤K≤1000,
1≤L≤100。

输入样例：

2 2
1 2 5
2 1 4
1 2 2

输出样例： 

14

A*算法核心思想： 反向计算最短路到终点的估计值

注意：当起点和终点一样时，K++

f [x]=h [x] + g [x] (起点到终点的估计距离 = 起点到x的真实距离 + x到终点的估计距离）

x到终点的估计距离我们可以通过Dijkstra算法逆向求出终点到各点的最短距离：

void Dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,T});
    memset(dist,0x3f,sizeof dist);
    dist[T]=0;
    while(heap.size())
    {
        auto it=heap.top();heap.pop();
        int distance=it.x,t=it.y;
        if(st[t])continue;
        st[t]=true;
        for(int i=rh[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}

接着就是从起点开始计算到终点的距离，我们需要将起点到终点距离小的优先出队，同一个点第几次出队就是第几短的路，那么就需要用到小顶堆了。

int star()
{
    if(dist[S]==0x3f3f3f3f) return -1;//若终点无法到达起点则返回-1
    priority_queue<PIII,vector<PIII> ,greater<PIII>> heap;
    heap.push({dist[S],{0,S}});
    while(heap.size())
    {
        auto it=heap.top();heap.pop();
        int distance=it.y.x,t=it.y.y;
        cnt[t]++;
        if(cnt[T]==K) return distance;//若终点第K次出队说明是第K短路
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(cnt[j]<K)
            {
                //起点到j的距离+j到终点的估计距离
                heap.push({distance+w[i]+dist[j],{distance+w[i],j}});
            }
        }
    }
    return -1;
}

完整代码：

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

#define x first
#define y second
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int N=2e4+5;

int h[N],rh[N],e[N],ne[N],w[N],idx;
int dist[N],cnt[N],n,m,S,T,K;
bool st[N];

void add(int h[],int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void Dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,T});
    memset(dist,0x3f,sizeof dist);
    dist[T]=0;
    while(heap.size())
    {
        auto it=heap.top();heap.pop();
        int distance=it.x,t=it.y;
        if(st[t])continue;
        st[t]=true;
        for(int i=rh[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}
int star()
{
    if(dist[S]==0x3f3f3f3f) return -1;
    priority_queue<PIII,vector<PIII> ,greater<PIII>> heap;
    heap.push({dist[S],{0,S}});
    while(heap.size())
    {
        auto it=heap.top();heap.pop();
        int distance=it.y.x,t=it.y.y;
        cnt[t]++;
        if(cnt[T]==K) return distance;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(cnt[j]<K)
            {
                heap.push({distance+w[i]+dist[j],{distance+w[i],j}});
            }
        }
    }
    return -1;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(rh,-1,sizeof rh);
    while(m--)
    {
        int a,b,c;cin>>a>>b>>c;
        add(h,a,b,c);
        add(rh,b,a,c);
    }
    cin>>S>>T>>K;
    if(S==T) K++;
    Dijkstra();
    cout<<star();
    return 0;
}