POJ 2449 A*+SPFA

A*算法求第k短路流程：

1）计算h[]，即当前点到t的估计值

　　若为有向图，建立反向图求出h[]。若为无向图，可直接求解h[]。可通过SPFA求解。

2）A*搜索

　　每次找到新节点就直接加入队列，计算出估价函数f[]=g[]+h[]，然后加入优先队列中。（此步不可优化，否则可能造成失解）

　　常用STL priority_queue实现，要注意默认是大根堆，可重载<实现小根堆。

3）若根入队k次，返回

ADD：

该题几个注意事项及优化：

　　a）若起始点h值==INF，不搜。

　　b）若一个点入队超过k次，不搜。

　　c）邻接表代替邻接矩阵，防止重边。

　　d）该题中若s==t，距离为0的路径不能计入。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <cmath>

#include <utility>

#include <vector>

#include <queue>

#include <map>

#include <set>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)>(y)?(y):(x))

#define INF 0x3f3f3f3f

#define N 1005

#define M 100005

using namespace std;

struct Edge

{

    int y,w,ne;

}e[M*],re[M*];

int x,y,w,n,m,s,t,k;

int be[N],all;

int rbe[N],rall;

int h[N],cnt[N];

bool vis[N];

struct Point

{

    int x,g;

    bool operator < (const Point T) const

    {

        return g+h[x]>T.g+h[T.x];

    }

};

void add(int x, int y, int w)

{

    e[all].y=y;

    e[all].w=w;

    e[all].ne=be[x];

    be[x]=all++;

}

void radd(int x, int y, int w)

{

    re[rall].y=y;

    re[rall].w=w;

    re[rall].ne=rbe[x];

    rbe[x]=rall++;

}

void SPFA(int s)

{

    queue< int > q;

    while(!q.empty())

        q.pop();

    for(int i=; i<=n; i++)

    {

        h[i]=INF;

        vis[i]=;

    }

    h[s]=;

    vis[s]=;

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        vis[u]=;

        for(int i=rbe[u]; i!=-; i=re[i].ne)

        {

            int v=re[i].y;

            if(h[v]>h[u]+re[i].w)

            {

                h[v]=h[u]+re[i].w;

                if(!vis[v])

                {

                    vis[v]=;

                    q.push(v);

                }

            }

        }

    }

}

int Astar(int s, int t, int k)

{

    SPFA(t);

    if(h[s]==INF) return -;

    priority_queue< Point > q;

    while(!q.empty())

        q.pop();

    memset(vis,,sizeof(vis));

    memset(cnt,,sizeof(cnt));

    Point cur,nxt;

    cur.x=s;

    cur.g=;

    q.push(cur);

    while(!q.empty())

    {

        cur=q.top();

        q.pop();

        if((++cnt[cur.x])>k) continue;

        if(cnt[t]==k)

            return cur.g;

        for(int i=be[cur.x]; i!=-; i=e[i].ne)

        {

            nxt.x=e[i].y;

            nxt.g=cur.g+e[i].w;

            q.push(nxt);

        }

    }

    return -;

}

void init()

{

    all=;

    memset(be,-,sizeof(be));

    rall=;

    memset(rbe,-,sizeof(rbe));

}

int main()

{

    scanf("%d%d",&n,&m);

    init();

    for(int i=; i<m; i++)

    {

        scanf("%d%d%d",&x,&y,&w);

        add(x,y,w);

        radd(y,x,w);

    }

    scanf("%d%d%d",&s,&t,&k);

    if(s==t) k++;

    printf("%d\n",Astar(s,t,k));

    return ;

}

/*

2 4

1 2 1

1 2 2

1 2 3

2 1 5

1 2 5

*/