题目描述

/
A 应用场景:
起点→终点的最短距离
状态空间 >> 1e10
启发函数减小搜索空间

A*算法:
优先队列存的是：从起点走到当前点的真实距离+从当前点到终点的估价距离，按从小到大排列
while(q.size())
t ← 优先队列的队头 小根堆
当终点第一次出队时 break;
从起点到当前点的真实距离 d_real
从当前点到终点的估计距离 d_estimate
选择一个估计距离最小的点 min(d_estimate)
for j in ne[t]:
将邻边入队

A*算法条件:
估计距离<=真实距离
d[state] + f[state] = 起点到state的真实距离 + state到终点的估计距离=估计距离
^
d[state] + g[state] = 起点到state的真实距离 + state到终点的真实距离=真实距离

一定是有解才有 d[i] >= d[最优] = d[u]+f[u]
f[u] >= 0

判重

对于BFS，在入队时判重
对于djk在出队时判重，因为只要出队第一次，就是正确的，之后这个点不需要再看了
A*：不需要判重！

估价函数

每个点到终点的最短距离

注意要判断起点可能到不了终点的情况，直接返回-1

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N=1010,M=200010;
int h[N],rh[N],ne[M],e[M],w[M],idx;
int dist[N],st[N];
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
int n,m,S,T,K;

void add(int h[],int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

//利用djk求估价函数,从终点求到每个点的最短距离
void djk()
{
    priority_queue<pii , vector<pii> , greater<pii>> heap;
    memset(dist,0x3f,sizeof dist);
    dist[T]=0;
    heap.push({0,T});
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second;
        int dis=t.first;
        if(st[ver]) continue;
        st[ver]=1;
        for(int i=rh[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dis+w[i])
            {
                dist[j]=dis+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}

int astar()
{
    priority_queue<piii , vector<piii> , greater<piii>> heap;
    //枚举所有点的所有情况，不需要判重
    //piii所存的含义为：评估值(真实值+评估值)，真实距离，该点编号
    // 按真实值+估计值 = d[j]+f[j] = dist[S,t] + w[t][j] + dist[j,T] 堆排
    // 其中真实值为distance+w[i]，distance为起点到第ver个点的距离，w[i]为ver到j的边，之和为起点到j的真真实距离
    heap.push({dist[S],{0,S}});
    if(dist[S] == 0X3f3f3f3f) return -1;
    int cnt=0;
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second.second;
        //dis为起点到ver的真实距离
        int dis=t.second.first;
        if(ver==T) cnt++;
        if(cnt==K) return dis;

        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            //其中dis+w[i]为真实值，起点到j的真实距离
            heap.push({dis+w[i]+dist[j],{dis+w[i],j}});
        }

    }
    return -1;
}


int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(rh,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(h,a,b,c);
        add(rh,b,a,c);
    }
    cin>>S>>T>>K;
    // 起点==终点时 则d[S→S] = 0 这种情况就要舍去 ,总共第K大变为总共第K+1大 
    if(S==T) K++;
    djk();
    cout << astar();
    return 0;
}