A*算法就是加了估价函数求最短路,每次从堆中取出 dis[i]+g[i]最小的那个节点，其中g[i]是i到目标节点的估计距离，这个估计距离不能比实际距离大。
这样可以避免一种情况：当前节点dis最小，但是实际上到达目标时花费较大，这样就增加了无用操作。
有许多例子，比如网格图中估价函数可以是曼哈顿距离。

例题：

K短路

代码：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
typedef long long ll;
using namespace std;
template<typename T>void in(T &x) {
    char ch = getchar();bool flag = 0;x = 0;
    while(ch < '0' || ch > '9') flag |= (ch == '-'), ch = getchar();
    while(ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    if(flag) x = -x;return ;
}
typedef pair<int,int> node;
#define maxn 1010
#define maxm 100010
struct edge{
    int v,nxt,c;
};
int k,s,t,n,m;
int g[maxn];

namespace spfa{
    int head[maxn];
    edge e[maxm];
    bool vis[maxn],inq[maxn];
    queue<int> q;
    void add(int u,int v,int t){
        e[++head[0]]={v,head[u],t};head[u]=head[0];
        return ;
    }
    void solve(){
        g[t] = 0;vis[t]=inq[t]=1;
        q.push(t);
        while( !q.empty() ) {
            int x = q.front();
            q.pop();
            inq[x]=0;
            for( int i = head[x]; i ; i = e[i].nxt ) {
                int y = e[i].v;
                if( vis[y] == 0 || g[y] > g[x] + e[i].c ) {
                    g[y]=g[x]+e[i].c;
                    vis[y]=1;
                    if(inq[y] == 0 )
                        q.push(y),inq[y]=1;
                }
            }
        }
        return ;
    }
}

namespace dij{
    edge e[maxm];
    int head[maxn],tim[maxn];
    priority_queue <node,vector<node>,greater<node> > q;
    void add(int u,int v,int t){e[++head[0]]={v,head[u],t};head[u]=head[0];return ;}

    void solve(){
        q.push( (node) {g[s],s} );
        while( q.size() ) {
            int x = q.top().second,dist=q.top().first-g[x];
            q.pop();
            tim[x]++;
            if(tim[t]==k){
                printf("%d",dist);
                return ;
            }
            for( int i = head[x]; i; i = e[i].nxt ) {
                int y = e[i].v;
                if(tim[y]!=k)
                    q.push(node{dist+e[i].c+g[y],y});
            }
        }
        printf("-1");
        return ;
    }
}

void input(){
    in(n);in(m);
    for(int a,b,l,i=1;i<=m;i++){
        in(a);in(b);in(l);
        spfa::add(b,a,l);
        dij::add(a,b,l);
    }
    in(s);in(t);in(k);
    if(s==t){
        k++;
    } 
}

int main(){
    input();
    spfa::solve();
    dij::solve();
    return 0;
}