[bzoj1598][Usaco08Mar]牛跑步_A*

牛跑步 bzoj-1598

题目大意：给你n个点，m条边的有向图。求从1到n的严格的第k短路。

注释：$1\le n\le 1000$，$1\le m \le 10,000$，$1\le k \le 100$。

想法：

　　A*：俗称机器人走路算法。就是说从一个点走到另一个点的最短路径，显然可以bfs。我们可以在bfs时设立估价函数来判断queue中先取出那个点。

　　比如说这道题，我们先将所有边存起来，先都连反向边。然后从n节点开始跑一遍堆优化dij表示这个点到n的最短路。然后我们从1号节点开始bfs。我们将所有遍历到的节点扔进堆，堆中的估价函数是从源点到当前状态的长度dis加上从当前节点到n的最短路。这样的话，第一个到的点一定是最短路，第二个同理，以此类推，知道我们在n节点已经接收到了k个不同的值，break输出答案即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <stdlib.h>

#define N 100010

using namespace std;

int ans[N];

int tot,head[N],to[N],nxt[N],val[N];

int H[N];

struct Node

{

	int dis,id;

	Node(){}

	Node(int dis_,int id_):dis(dis_),id(id_){}

	inline bool operator < (const Node &x) const

	{

		return dis+H[id]>x.dis+H[x.id];

	}

};

priority_queue<Node> q;

priority_queue<pair<int,int> >Q;

bool v[N];

inline void add(int x,int y,int z)

{

	to[++tot]=y;

	val[tot]=z;

	nxt[tot]=head[x];

	head[x]=tot;

}

int x[N],y[N],z[N];

int n;

bool vis[N];

void Dij()

{

	memset(H,0x3f,sizeof H);

	memset(vis,0,sizeof vis);

	H[n]=0;

	Q.push(make_pair(0,n));

	while(!Q.empty())

	{

		int a=Q.top().second;

		Q.pop();

		if(vis[a]) continue;

		vis[a]=1;

		for(int i=head[a];i;i=nxt[i])

		{

			if(H[to[i]]>H[a]+val[i])

			{

				H[to[i]]=H[a]+val[i];

				Q.push(make_pair(-H[to[i]],to[i]));

			}

		}

	}

}

int cnt=0;

void A_xing(int num)

{

	q.push(Node(0,1));

	while(!q.empty())

	{

		Node t=q.top();

		q.pop();

		int a=t.id;

		int distance=t.dis;

		if(a==n)

		{

			ans[++cnt]=distance;

			// puts("Fuck");

		}

		if(cnt==num) return;

		for(int i=head[a];i;i=nxt[i])

		{

			int w=distance+val[i];

			/*if(!mp.count(make_pair(w,to[i])))

			{

				mp[make_pair(w,to[i])]=1;

				q2.push(node(w,to[i]));

			}*/

			q.push(Node(w,to[i]));

		}

	}

}

int main()

{

	int r,k;

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

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

	{

		scanf("%d%d%d",&x[i],&y[i],&z[i]);

		add(x[i],y[i],z[i]);

	}

	Dij();

	memset(head,0,sizeof head);

	tot=0;

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

	{

		add(y[i],x[i],z[i]);

	}

	// for(int i=1;i<=n;i++)

	// {

	// 	printf("%d:%d\n",i,H[i]);

	// }

	A_xing(k);

	for(int i=1;i<=k;i++)

	{

		if(i<=cnt) printf("%d\n",ans[i]);

		else printf("-1\n");

	}

	return 0;

}

小结：这种毒瘤算法好像少接触为妙。

巴特西

[bzoj1598][Usaco08Mar]牛跑步_A*_Dijkstra

最新文章

热门文章