解题报告 P2901 [USACO08MAR]Cow Jogging G

题目内容

P2901

给定一有向带权图，求从 n 到 1 的前 k 短路的长度

解题思路

求 k 短路的一个常用的方法是使用 A*，怎么求呢？

首先，预处理出所有点到 1 的最短距离（使用反向图跑最短路），然后从 n 开始进行广搜，只不过队列改为优先队列，估价方式为 f+dis[now] 小的先出队，其中 f 为已经走过的路，dis[now] 为 now 到 1 的最短距离，这样子进行估价可以使估的价一定小于等于实际代价。然后 A* 会根据估价从小到大依次进行扩展，最先进入到 1 号的就是最短路，随后次短路，第三短路。。。会依次进入到 1 号点，每次输出走过路径长即可。

#include <queue>
#include <cstdio>
#include <vector>
#include <cctype>
#include <utility>
#include <cstring>

typedef long long ll;
using namespace std;

const int maxn=1e3+5;

struct node
{
    ll pos,f;
    node(){}
    node(int _p,int _f)
    {
        pos=_p;
        f=_f;
    }
};

struct edge
{
    ll from,to,dist;
    edge(){}
    edge(ll u,ll v,ll w)
    {
        from=u;
        to=v;
        dist=w;
    }
};

//快读省略

vector<edge> g1[maxn],g2[maxn];//g1存正向图，g2存反向图
ll dis[maxn],n,m,k;
bool vis[maxn];

bool operator<(const node &_a,const node &_b)
{
    return _a.f+dis[_a.pos]>_b.f+dis[_b.pos];
}

void dijsktra()//反向跑dij获取每个点的距离
{
    priority_queue<pair<ll,ll>, vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
    memset(dis,0x3f,sizeof(vis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g2[now])
            {
                if(dis[e.to]>dis[now]+e.dist)
                {
                    dis[e.to]=dis[now]+e.dist;
                    q.push(make_pair(dis[e.to],e.to));
                }
            }
        }
    }
    return;
}

void astar()//开始A*
{
    priority_queue<node> q;
    q.push(node(n,0));
    while(!q.empty())
    {
        ll now=q.top().pos,f=q.top().f;
        q.pop();
        if(now==1)//如果到终点了
        {
            printf("%lld\n",f);//直接输出
            if(!(--k))//如果已经求完前k短路，结束
                return;
        }
        else
            for(auto i:g1[now])//然后就是扩展
                q.push(node(i.to,i.dist+f));
    }
    while(k--)//如果还有没搞完的
        printf("-1\n");
    return;
}

inline void ins(ll u,ll v,ll w)
{
    g1[u].push_back(edge(u,v,w));
    g2[v].push_back(edge(v,u,w));
    return;
}

int main()
{
    n=read(),m=read(),k=read();
    ll u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        ins(u,v,w);
    }
    dijsktra();
    astar();
    return 0;
}