例题

题目描述

Bessie 来到一个小农场，有时她想回老家看看她的一位好友。她不想太早地回到老家，因为她喜欢途中的美丽风景。她决定选择K短路径，而不是最短路径。

农村有 R (1≤R≤100,000) 条单向的路，每条路连接 N (1≤N≤10000) 个结点中的两个。结点的编号是 1..N。Bessie 从结点 1出发，她的朋友（目的地）在结点 N。

同一个点可以多次经过。K短路的定义：假设从1出发，有M条长度不同的路径可以到达点N，则K短路就是这M条路径中第K小的路径长度。

输入格式

Line 1: 三个用空格分隔的整数 N，R，K（（1≤n≤10000,1≤R≤100000,1≤K≤10000）

Lines 2..R+1: 每行包含三个用空格分隔的整数x,y,len（1≤x,y≤n,1≤len≤10000），表示x到y有一条长度为len的单向道路。

输出格式

输出包括一行，一个整数，第K短路的长度。

样例输入

4 4 2

1 2 100

2 4 200

2 3 250

3 4 100

样例输出

450

做法

考虑用A*算法。

我们知道A*算法有个性质：

设h(i)表示从i到终点的估计距离，设h*(i)表示i到终点的实际距离

1、当h(i) < h*(i)时，程序慢，但是保证找到最优解

2、当h(i) = h*(i)时，程序快，并且保证找到最优解

3、当h(i) > h*(i)时，程序快，但是不保证找到最优解

所以，若有元素t在堆顶弹出，若其为终点，且是第K次出堆，则答案为它走过的距离(t.g)

所以，首先我们预处理出h(i)。怎么求？我们可以考虑以上第二种方案。

因为我们可以先将所有的边的方向反过来，以N为起点，求出每一个点到N的最短路径。

最短路径都会吧？跑一遍SPFA（dijsktra没试过）。

h(i)为i到N的最短路径。

接下来开始A*！开一个堆，每次取出f（1到N估计总距离，f(i)=g(i)+h(i)）最小的，然后往与它相连的点拓展。弹出后可以再进堆。若弹出的点为终点且是第K次出堆，则输出答案。

有一种坑了我很久的情况：当两条路径一样时，就当做一条看，加特判就行了。

但是不要乱加特判，要看题目，知道它要我们求什么。

代码实现（C++）

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,r,k;//如题

struct Edge

{

    int x,y,len;

    Edge* las;//记录上一个和此次的x一样的边

} e1[100001],e2[100001];//e1是正向的，e2是反向的（前向星）

Edge *last1[10001],*last2[10001];//last[i]表示x为i的最后一条边

int h[10001];//见“做法”

const int SIZE=1000000;

int que[SIZE];

bool in_que[10001];

inline void spfa(int);

struct Node

{

    int n,g,f;  //n：在第n个点；g：已走g的路径；f：估计距离

} heap[SIZE];//堆

bool cmp(const Node& a,const Node& b)//比较函数

{

    return a.f>b.f;

}

inline void A_star(int,int);

int main()

{

    scanf("%d%d%d",&n,&r,&k);

    int i,j=0,x,y,len;

    for (i=1;i<=r;i++)

    {

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

        while(getchar()!='\n');//这句话是因为数据有问题才加上去的，不用管

        j++;

        e1[j]={x,y,len,last1[x]};//新增一条边

        last1[x]=e1+j;

        e2[j]={y,x,len,last2[y]};

        last2[y]=e2+j;

    }

    spfa(n);

    A_star(1,n);

}

inline void spfa(int u)

{

    memset(h,127,sizeof h);

    h[u]=0;

    int head=0,tail=1;

    Edge* to;

    que[1]=u;

    in_que[u]=1;

    do

    {

        if (++head==SIZE)

            head=0;

        for (to=last2[que[head]];to;to=to->las)

        {

            if (h[to->x]+to->len>=h[to->y])

                continue;

            h[to->y]=h[to->x]+to->len;

            if (in_que[to->y])

                continue;

            if (++tail==SIZE)

                tail=0;

            que[tail]=to->y;

            in_que[to->y]=1;

        }

        in_que[que[head]]=0;

    }

    while (head!=tail);

}

inline void A_star(int u,int v)

{

    int nh=1,cnt=0,ans;

    Edge* to;

    *heap={u,0,h[u]};

    while (nh)

    {

        if (heap->n==v && heap->g!=ans)//特判相等的情况

        {

            ans=heap->g;

            if (++cnt==k)

            {

                printf("%d\n",heap->g);

                return;

            }

        }

        for (to=last1[heap->n];to;to=to->las)

        {

            heap[nh].n=to->y;

            heap[nh].g=heap->g+to->len;

            heap[nh].f=heap[nh].g+h[to->y];

            nh++;

            push_heap(heap,heap+nh,cmp);//加入堆

        }

        pop_heap(heap,heap+nh,cmp);

        nh--;//弹出堆

    }

}

巴特西

A*算法——第K短路

例题