「USACO08MAR」Cow Jogging

题意：贝西尝到了懒惰的恶果——为了减肥，她不得不决定每周花几次时间在牛棚和池塘之间慢跑。但贝西并不想太累，所以她打算只跑从牛棚到池塘的下坡路，然后再慢慢地从池塘走回牛棚。同时，贝西也不想跑得太远，所以她只想沿着通向池塘的最短路径跑步。在牧场里，每条道路连接了两个结点(这些结点的编号为 $1$ 到 $N$ ， $1\le N\le 1000$ ）。另外，如果 $X>Y$ ，说明结点 $X$ 的地势要高于 $Y$ ，所以下坡的道路是从 $X$ 通向 $Y$ 的，贝西所在牛棚的编号为 $N$ (最高点)，池塘的编号为 $1$ (最低点)。而然，一周之后，贝西对单调的路线厌倦了，她希望每天可以跑不同的路线，比如说，最好能有 $K (1\le K\le 100)$ 种不同的选择。为了不至于跑得太累，她希望这 $K$ 条路径是从牛棚到池塘的最短的 $K$ 条路径。请帮助贝西算算她的运动量，即找出网络里最短的 $K$ 条路径的长度。假设每条道路用 $(X _i,Y _i,D _i)$ 表示，其中 $1\le Y _i <X _i\le N$ ，表示这条道路从 $X _i$ 出发到 $Y _i$ ，其长度为 $D _i (1\le D _i\le 1000000)$ 。

一道 K短路 的模板题。

根据 dijkstra 的思想，当一个点 $u$ 第 $k$ 次从优先队列中被弹出时，那么得到的就是从起点到 $u$ 的 k短路。

使用优先队列在最坏情况下的复杂度为 O(K*(N+M)*log(N+M))，我们可以用 A* 算法加速。

`A*` 算法

主要作用是加速优先队列搜索速率，通过设置估价函数来改变优先队列取出的顺序。

我们设置一个估价函数，以任意状态为输入，计算出从该状态到目标状态的估计值，在搜索中取出队列当前代价+未来估价的最小状态扩展。

设当前状态 state 到目标状态所需代价的估计值为 f(state)；

设在未来搜索中，实际求出从当前状态 state 到目标状态的最小代价为 g(state)；

对于任意 state，应该满足 f(state) $\le$ g(state)，即一直满足估价比实际更优。

根据估价函数的设计准则，我们在第 $K$ 短路中从 $x$ 到终点 $1$ 的估计距离 $f(x)$ 应该不大于从第 $K$ 短路中从 $x$ 到终点 $1$ 的实际距离 $g(x)$ 。

很容易想到，我们把估价函数 $f(x)$ 设为从 $x$ 到 $1$ 的最短路长度即可。

最后算法流程如下：

预处理出 $f(x)$ ，即建反图从终点 $1$ 求一次最短路；
建立一个二叉堆，存储二元组 $(x,dis+f(x))$ ， $dis$ 为从起点 $n$ 到 $x$ 走的距离，初始只有 $(n,0+f(n))$ ；
从堆中取出 $dis+f(x)$ 最小的二元组 $(x,dis+f(x))$ ，然后访问每条边 $(x,y)$ 扩展，如果节点 $y$ 被取出的次数没达到 $K$ ，就把新的二元组 $(y,dis+w(x,y)+f(y))$ 插入堆；
重复 $2\sim 3$ 步，直到第 $K$ 次取出包含终点 $1$ 的二元组，就得到了第 $K$ 短路。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e3+10,maxm=1e4+100;
int n,m,k;
int head1[maxn],cnt1;
int head2[maxn],cnt2;
int dis[maxn],ex[maxn];
int tim[maxn],ans[maxn],p;
queue<int> q1;
priority_queue<pair<int,int> > q2;
struct node
{
	int next;
	int to;
	int num;
}e1[maxm<<1],e2[maxm<<1];
void add1(int from,int to,int num)
{
	e1[++cnt1].next=head1[from];
	e1[cnt1].to=to;
	e1[cnt1].num=num;
	head1[from]=cnt1;
}
void add2(int from,int to,int num)
{
	e2[++cnt2].next=head2[from];
	e2[cnt2].to=to;
	e2[cnt2].num=num;
	head2[from]=cnt2;
}
void spfa(int x)
{
	memset(dis,0x3f,sizeof(dis));
	memset(ex,0,sizeof(ex));
	while(!q1.empty())
		q1.pop();
	dis[x]=0;
	ex[x]=1;
	q1.push(x);
	while(!q1.empty())
	{
		int u=q1.front();
		q1.pop();
		ex[u]=0;
		for(int i=head2[u];i;i=e2[i].next)
		{
			int v=e2[i].to;
			if(dis[v]>dis[u]+e2[i].num)
			{
				dis[v]=dis[u]+e2[i].num;
				if(!ex[v])
				{
					ex[v]=1;
					q1.push(v);
				}
			}
		}
	}
}
void A_star(int x)
{
	q2.push(make_pair(-dis[x],x));
	while(!q2.empty())
	{
		int u=q2.top().second;
		int id=-q2.top().first;
		q2.pop();
		if(u==1)
			ans[++p]=id;
		if(p==k)
			return ;
		for(int i=head1[u];i;i=e1[i].next)
		{
			int v=e1[i].to;
			q2.push(make_pair(-(id-dis[u]+e1[i].num+dis[v]),v));
		}
	}
	return ;
}
int main()
{
	memset(ans,-1,sizeof(ans));
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(a<b)
			swap(a,b);
		add1(a,b,c);
		add2(b,a,c);
	}
	spfa(1);
	A_star(n);
	for(int i=1;i<=k;i++)
		printf("%d\n",ans[i]);
	return 0;
}

A* 算法

`A*` 算法