cogs 133. [USACO Mar08] 牛跑步 A*k短路算法

by  http://blog.csdn.net/jarily/article/details/8871968
/* 
 *算法引入： 
 *在单源点最短路径问题中,实际运用时还需知道最短路径外,次短路或者第三短路; 
 *即要知道多条最短路,并排出其长度增加的顺序,即为K最短路问题; 
 * 
 *算法思想： 
 *单源点最短路径+高级搜索A*; 
 *A*算法结合了启发式方法和形式化方法; 
 *启发式方法通过充分利用图给出的信息来动态地做出决定而使搜索次数大大降低; 
 *形式化方法不利用图给出的信息,而仅通过数学的形式分析; 
 * 
 *算法通过一个估价函数f(h)来估计图中的当前点p到终点的距离,并由此决定它的搜索方向; 
 *当这条路径失败时,它会尝试其他路径; 
 *对于A*,估价函数=当前值+当前位置到终点的距离,即f(p)=g(p)+h(p),每次扩展估价函数值最小的一个; 
 * 
 *对于K短路算法来说,g(p)为当前从s到p所走的路径的长度;h(p)为点p到t的最短路的长度; 
 *f(p)的意义为从s按照当前路径走到p后再走到终点t一共至少要走多远; 
 * 
 *为了加速计算,h(p)需要在A*搜索之前进行预处理,只要将原图的所有边反向,再从终点t做一次单源点最短路径就能得到每个点的h(p)了; 
 * 
 *算法步骤： 
 *(1),将有向图的所有边反向,以原终点t为源点,求解t到所有点的最短距离; 
 *(2),新建一个优先队列,将源点s加入到队列中; 
 *(3),从优先级队列中弹出f(p)最小的点p,如果点p就是t,则计算t出队的次数; 
 *如果当前为t的第k次出队,则当前路径的长度就是s到t的第k短路的长度,算法结束; 
 *否则遍历与p相连的所有的边,将扩展出的到p的邻接点信息加入到优先级队列; 
 * 
 *算法测试： 
 *http://www.cogs.pro/cogs/problem/problem.php?pid=133 
 * 
 *题目大意： 
 *求从s到t的第k短路的长度; 
 */

133. [USACO Mar08] 牛跑步

★★★ 输入文件：cowjog.in 输出文件：cowjog.out 简单对比
时间限制：1 s 内存限制：128 MB

很快,

请帮助

题目名称: cowjog

输入格式:

样例输入 (cowjog.in):

输出格式:

样例输出 (cowjog.out):

输出解释:

路径分别为

/*
    k短路：
    建立反向图，计算终点到起点的单源最短路，最后A*求解最短路 
    A*算法：
    新建一个优先队列,将源点s加入到队列中; 
    从优先级队列中弹出估值函数f()最小的点p,如果点p就是t,则计算t出队的次数;
    f(n)=g(n)+h(n)  g(n) 表示走到当前点的路程  
    h(n) 表示当前位置到终点的距离（在反向跑时已经计算出） 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>

using namespace std;
const int N=10010;
const int INF=99999999; 

int now1=1,now2=1;
int dis[N],head1[N],head2[N];
bool vis[N];
int ans[N];
int n,m,k,js;
struct fan{
    int u,v,w,nxt;
}F[N];
struct zheng{
    int u,v,w,nxt;
}Z[N];
struct node{
    int point,noww,will;
}now,topp,nxt;

inline int read()
{
    int x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}

inline void addzheng(int u,int v,int w)
{Z[now1].v=v;Z[now1].w=w;Z[now1].nxt=head1[u];head1[u]=now1++;}

inline void addfan(int u,int v,int w)
{F[now2].v=v;F[now2].w=w;F[now2].nxt=head2[u];head2[u]=now2++;}

bool operator < (node a,node b)
{return a.will>b.will;}

inline void spfa(int start)
{
    queue<int>q;
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[start]=0;vis[start]=1;
    q.push(start);
    while(!q.empty())
    {
        int ttop=q.front();q.pop();
        vis[ttop]=0;
        for(int i=head2[ttop];~i;i=F[i].nxt)
            if(dis[F[i].v]>dis[ttop]+F[i].w)
                {dis[F[i].v]=dis[ttop]+F[i].w;if(!vis[F[i].v])vis[F[i].v]=1,q.push(F[i].v);}
    }
}

inline void Astar(int start,int endd)
{
    if(dis[start]==INF||start==endd)return ;
    now.point=start,now.noww=0;now.will=dis[start];
    priority_queue<node>q;
    q.push(now);
    while(!q.empty())
    {
        topp=q.top();
        q.pop();
        if(topp.point==endd){ans[++js]=topp.noww;if(js==k)return ;}
        for(int i=head1[topp.point];~i;i=Z[i].nxt)
            {nxt.point=Z[i].v;nxt.noww=topp.noww+Z[i].w;nxt.will=nxt.noww+dis[Z[i].v];q.push(nxt);}
    }
}

int main()
{
    freopen("cowjog.in","r",stdin);
    freopen("cowjog.out","w",stdout);
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++)head1[i]=head2[i]=-1;
    for(int i=1;i<=m;i++)
        {int u=read(),v=read(),w=read();addzheng(u,v,w);addfan(v,u,w);}
    spfa(1);
    Astar(n,1);
    for(int i=1;i<=js;i++)printf("%d
",ans[i]);
    for(int i=js+1;i<=k;i++)printf("-1
");
    return 0;
}