莫欺少年穷，修魔之旅在这开始—>算法提高课题解

保姆级注释，看不懂你炸我

A*算法

当估价函数为0时，就是 Dijkstra 算法；当权值都为1时，就是 BFS

思路：

1. 第 K 短路，就是终点出队 K 次的距离。注意：当起点和终点一样时，K ++
2. 只要从 S 能到达 T，就一定存在第K短路，故不存在则一定不能从 S 到达 T
3. 估价函数：从该点到终点的最短距离，即求一遍 dijkstra，大于等于 0，小于等于真实值
4. 取出堆顶，记录出队次数，把该点能枚举到的所有点都放入小根堆

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
typedef pair<int,PII> PIII;

const int N = 1010, M = 20010;

int n,m,S,T,K;
int h[N],rh[N],e[M],w[M],ne[M],idx;
int dist[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++;
}

//从该点到终点的最短距离dist，不仅大于等于0，更是小于等于真实距离
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 t=heap.top();
        heap.pop();

        int ver=t.second;
        if(st[ver]) continue;
        st[ver]=true;

        for(int i=rh[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[ver]+w[i]<dist[j])
            {
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}

int astar()
{
    //小根堆初始化，第一元素：从起点到终点的估价距离；第二元素：从起点到该点的真实距离；第三元素：该点
    priority_queue<PIII,vector<PIII>,greater<PIII>> heap;
    heap.push({dist[S],{0,S}});

    //说明从终点是不连通的点
    if(dist[S]==0x3f3f3f3f) return -1;

    while(heap.size())
    {
        //取出堆顶：从起点到终点的估价距离最小
        auto t=heap.top();
        heap.pop();

        int ver=t.y.y,distance=t.y.x;

        //记录该状态出队次数
        cnt[ver]++;
        if(cnt[T]==K) return distance;

        //枚举该点能够到达所有点
        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            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;

    //当两个点相同时，astar会直接return，故K++
    if(S==T) K++;

    dijkstra();

    cout<<astar()<<endl;

    return 0;
}