K短路学习笔记

K短路，顾名思义，是让你求从$s$到$t$的第$k$短的路。

暴力当然不可取，那么我们有什么算法可以解决这个问题？

--------------------------

首先，我们要维护一个堆。

struct node

{

    int dist,pos;

    bool operator <(const node&x) const

    {

        return dist>x.dist;

    }

}

priority_queue<node> q;

这个堆是用来干什么的？

----------------------------------------------

这时候要提到一种新算法：A*算法。

估价函数：$f[i]=g[i]+h[i]$。其中，$g[i]$是从起点$s$走，按照这条路径到当前点已经走了多少路程，$h[i]$是当前点到终点$t$的最短路。

我们用之前开设的堆来维护这个估价函数，这样到达第k次终点$t$的路径即为所求。

Code（这里是[SDOI2010]魔法猪学院的A*算法）:

void Astar(int kk)

{

    priority_queue<SKT> q;

    memset(vis,,sizeof(vis));

    x.pos=;x.dist=0.0;x.h=0.0;

    q.push(x);

    while(!q.empty())

    {

        int now=q.top().pos;double d=q.top().dist;double hh=q.top().h;q.pop();

        if (d>E) return;

        vis[now]++;

        if (now==n){ans++;E-=d;continue;}

        if (vis[now]>kk) continue;

        for (int i=head[now];i;i=edge[i].next)

        {

            int to=edge[i].to;

            SKT Faker;

            Faker.pos=to;Faker.h=hh+edge[i].dis;Faker.dist=Faker.h+dis[to];

            q.push(Faker);

        }

    }

}

----------------------------------

每个点到终点$t$的最短路怎么求？很简单，我们只要在建图的时候再建一个反向图，从终点跑单源最短路径即可。

Code:

void spfa()

{

    for (int i=;i<=n;i++) dis[i]=0x3f3f3f3f;

    queue<int> q;

    q.push(n);dis[n]=0.0;vis[n]=;

    while(!q.empty())

    {

        int now=q.front();q.pop();vis[now]=;

        for (int i=Head[now];i;i=Edge[i].next)

        {

            int to=Edge[i].to;

            if (dis[to]>dis[now]+Edge[i].dis)

            {

                dis[to]=dis[now]+Edge[i].dis;

                if (!vis[to]) q.push(to),vis[to]=;

            }

        }

    }

}

----------------------------

例题：[USACO08MAR]Cow Jogging G

近乎于K短路的裸题，只需要注意$u$大于$v$即可。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=;

const int maxm=;

int dis[maxn],vis[maxn];

int n,m,k;

struct SKT {

    int v;

    int dist;

    bool operator < (const SKT&p) const {

        return dist+dis[v]>p.dist+dis[p.v];

    }

};

SKT x;

struct Node

{

    int next,to,dis;

}edge[maxm],cont[maxm];

int heade[maxm],headc[maxm],cnt;

inline void add(int from,int to,int dis)

{

    edge[++cnt].next=heade[from];

    edge[cnt].to=to;

    edge[cnt].dis=dis;

    heade[from]=cnt;

    cont[cnt].next=headc[to];

    cont[cnt].to=from;

    cont[cnt].dis=dis;

    headc[to]=cnt;

}

inline int read()

{

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if (ch=='-') f=-;ch=getchar();}

    while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void spfa()

{

    queue<int> q;

    for (int i=;i<=n;i++) dis[i]=0x7fffffff;

    q.push();dis[]=;vis[]=;

    while(!q.empty())

    {

        int now=q.front();q.pop();vis[now]=;

        for (int i=headc[now];i;i=cont[i].next)

        {

            int to=cont[i].to;

            if (dis[to]>dis[now]+cont[i].dis)

            {

                dis[to]=dis[now]+cont[i].dis;

                if (!vis[to]) q.push(to),vis[to]=;

            }

        }

    }

}

void Astar()

{

    int ans=;

    priority_queue<SKT> q;

    x.v=n;x.dist=;

    q.push(x);

    while(!q.empty())

    {

        SKT now=q.top();q.pop();

        if (now.v==) printf("%d\n",now.dist),++ans;

        if (ans==k) return;

        for (int i=heade[now.v];i;i=edge[i].next)

        {

            int to=edge[i].to;

            if (to<now.v)

            {

                SKT Faker=now;

                Faker.v=to;Faker.dist=now.dist+edge[i].dis;

                q.push(Faker);

            }

        }

    }

    while(ans<k) cout<<-<<endl,++ans;

    return;

}

signed main()

{

    n=read(),m=read(),k=read();

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

    {

        int x=read(),y=read(),z=read();

        if (x>y) add(x,y,z);

    }

    spfa();

    Astar();

    return ;

}

巴特西

K短路学习笔记

最新文章

热门文章

巴特西

K短路 学习笔记

最新文章

热门文章

K短路学习笔记