K短路(A*)

在BFS搜索中，始点S第一次到达目标点E的路径是最短的，那再搜索中第k次到达目标点E就是第K短了。但这样很容易超时。因此介绍一种搜索算法A* （启发式搜索）

A*简单的说，它可以用公式表示为，其中，是从始点经由节点到的估价函数，是在状态空间中从x到n的实际代价，是从到的最佳路径估计代价。在设计中，要保证 (到的实际代价)。这一点很重要，越接近真实值，速度越快。

• （为实际问题的代价值）

• 当就是,就是

• 表示从初始结点到任意结点的代价，表示从结点到目标点的启发式评估代价

启发式函数可以控制A*的行为：

1. 如果，则只有起作用，此时A*演变成算法，这保证能找到最短路径。
2. 如果经常都比从移动到目标的实际代价小（或者相等），则A*保证能找到一条最短路径。越小，A*扩展的结点越多，运行就得越慢。
3. 如果精确地等于从移动到目标的代价，则A*将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（指让精确地等于实际值）。只要提供完美的信息，A*会运行得很完美，认识这一点很好。
4. 如果有时比从移动到目标的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。
5. 如果比大很多，则只有起作用，A*演变成BFS算法。

• 了解更多A*

K短路中为节点的过估价函数，则 ; 就是我们所说的‘启发式函数’，是节点到目标点的最小距离,
表示始点到节点的距离
1.将有向图的所有边反向,以原终点为源点,求解到所有点的最短距离，即 ;

2. 新建一个优先队列,将源点加入到队列中，队列中维护的是估价函数的值;
3. 从优先级队列中弹出 最小的点 ,如果点就是,则计算出队的次数;
   如果当前为 的第 次出队,则当前路径的长度就是 到 的第 短路的长度,算法结束;
   否则遍历与相连的所有的边,将扩展出的到x的邻接点信息加入到优先级队列;

Remmarguts' Date

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
const int M=1e5+100;
int headz[M],cntz;//正向存图
int headf[M],cntf;//反向存图
struct node
{
    int v,w,nxt;
} edgez[M],edgef[M];
int dis[10010];//h(x)
int vis[10010];
struct mat
{
    int v;
    int w;
    friend bool operator <(const mat x,const mat y)
    {
        return x.w+dis[x.v]>y.w+dis[y.v];//按照g(x)+h(x)<g(y)+h(y)
    }
} now,nxt;
void init( )
{
    memset(headz,-1,sizeof(headz));
    memset(headf,-1,sizeof(headf));
    cntz=cntf=0;
}
void addz(int x,int y,int w)
{
    edgez[++cntz].nxt=headz[x];
    edgez[cntz].v=y;
    edgez[cntz].w=w;
    headz[x]=cntz;
}
void addf(int x,int y,int w)//反向存图
{
    edgef[++cntf].nxt=headf[x];
    edgef[cntf].v=y;
    edgef[cntf].w=w;
    headf[x]=cntf;
}
void Dijkstra(int x)//反向遍历 求出终点到各个节点的最小距离
{
    memset(vis,0,sizeof(vis));
    memset(dis,INF,sizeof(dis));
    dis[x]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >qu;
    qu.push(make_pair(0,x));
    while(!qu.empty( ))
    {
        int u=qu.top().second;
        qu.pop( );
        if(!vis[u])
        {
            vis[u]=1;
            for(int i=headf[u]; i!=-1; i=edgef[i].nxt)
            {
                int v=edgef[i].v;
                if(dis[v]>dis[u]+edgef[i].w)
                {
                    dis[v]=dis[u]+edgef[i].w;
                    qu.push(make_pair(dis[v],v));
                }
            }
        }
    }
}
int Astar(int x,int y,int k)//正向遍历A*求出第K短路
{
    if(dis[x]==INF)
    {
        return -1;
    }
    int cnt=0;
    priority_queue<mat>qu;
    now.v=x;
    now.w=0;
    qu.push(now);
    while(!qu.empty( ))
    {
        now=qu.top( );
        qu.pop( );
        if(now.v==y)
        {
            cnt++;
            if(cnt==k)
            {
                return now.w;
            }
        }
        for(int i=headz[now.v]; i!=-1; i=edgez[i].nxt)
        {
            int v=edgez[i].v;
            nxt.v=v;
            nxt.w=edgez[i].w+now.w;
            qu.push(nxt);
        }
    }
    return -1;
}
int main( )
{
    int n,m,k,x,y,w;
    init( );
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        addz(x,y,w);
        addf(y,x,w);
    }
    scanf("%d%d%d",&x,&y,&k);
    Dijkstra(y);
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<dis[i]<<" ";
    // }
    // cout<<endl;
    if(x==y)
    {
        k++;
    }
    int ans=Astar(x,y,k);
    cout<<ans<<endl;
    return 0;
}