A*

A*其实就是优化的bfs，让过程更趋近于正确答案，再bfs的基础上多加了个预估函数，依据这个预告函数排序bfs的顺序。

题：poj2449

http://poj.org/problem?id=2449

题目大意：求出s到t的第k短路大小

题目思路：如果单用优先队列，那就是从s开始疯狂试探，然后一直到取t第k次的时候就是答案。但是很明显有个缺点，就是他需要走很多无谓的路。

所以我们需要用到A*算法。A*算法就是多了个估值函数。这里用的是该点到t的最短路值作为估值。

这样的话，就可以少走很多路，因为知道后来的情况，所以优先队列开头的都是比之前瞎走更加逼近正确答案的点，也就会更快可以将t取出k次。

这里最短路可以通过建反图获得t到各点的最短路也就变成了各点到t的最短路。有两个注意点，一个是如果s到t的距离是无限大，那么就不用继续直接输出-1，

还有一个是如果s=t那么需要k++，因为自己到自己距离是0，按照题意不能算第一短的路。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int M=1e5+5;
const int inf=0x3f3f3f3f;
int tot,head[M],rhead[M],dis[M],cnt[M],vis[M];
struct E{
    int v,w,nextt;
}e[M],re[M];
void addedge(int u,int v,int w){
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nextt=head[u];
    head[u]=tot;
    re[tot].v=u;
    re[tot].w=w;
    re[tot].nextt=rhead[v];
    rhead[v]=tot++;
}
void spfa(int s,int n){
    for(int i=0;i<=n;i++)
        cnt[i]=0,dis[i]=inf,vis[i]=0;
    queue<int>que;
    que.push(s);
    dis[s]=0;
    cnt[s]=1;
    while(!que.empty()){
        int  u=que.front();
        que.pop();
        vis[u]=0;
        for(int i=rhead[u];~i;i=re[i].nextt){
            int v=re[i].v;
            if(dis[v]>dis[u]+re[i].w){
                dis[v]=dis[u]+re[i].w;
                if(!vis[v]){
                    que.push(v);
                    vis[v]=1;
                    if(++cnt[v]>n)
                        return ;
                }
            }
        }
    }
    return ;
}
//让dist小的先出队
struct node{
    /*friend bool operator<(node n1,node n2){
        return n1.dist>n2.dist;
    }*/
    int x,dist;
    bool operator < (const node &b)const{
        return this->dist>b.dist;
    }
};
priority_queue<node>q;
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        tot=0;
        for(int i=0;i<=n;i++)
            head[i]=-1,rhead[i]=-1;
        while(m--){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
        }
        int s,t,k;
        scanf("%d%d%d",&s,&t,&k);
        spfa(t,n);
        if(dis[s]==inf){
            puts("-1");
            continue;
        }
        while(!q.empty())
            q.pop();
        node sta;
        sta.x=s,sta.dist=dis[s];
        q.push(sta);
        int ans=-1,num=0;
        if(s==t)
            k++;
        while(!q.empty()){
            node temp=q.top();
            q.pop();
            int u=temp.x;
            if(u==t){
                num++;
                if(num==k){
                    ans=temp.dist;
                    break;
                }
            }
            for(int i=head[u];~i;i=e[i].nextt){
                int v=e[i].v;
                node close;
                close.x=v;
                close.dist=temp.dist-dis[u]+dis[v]+e[i].w;
                q.push(close);
            }
        }
        printf("%d
",ans);
    }
    return 0;
}