A* K短路

注：\(A*\) 求解K短路效率极其低下，时间复杂度\(O(nklog\ n)\),空间视题目而定，因为本质是爆搜，可求解数据范围较小的题目。

我们使用\(A*\)求解k短路:

首先需要预处理出估价函数。对于原图建立反向图，然后跑终点的单源最短路。用终点到这个点的距离作为\(A*\)的估价函数，可以完全保证搜索准确性。

然后我们跑\(A*\)。每次从优先队列里取出当前步数与估价函数之和最小的点并扩展其所有边。对于每个状态我们需要开一个标记数组（或者路径数组也可以），防止重复经过同一个点。

此时我们每次从优先队列取出的都是当前最短路径，当一个点第k次被取出时，这条路径就是k短路。

提供一道毒瘤例题P4467 SCOI2007k短路

这题似乎是公认的卡A*(只卡了一个点，所以被用作\(A*\)求k短路的模板题)

特判用代码:

if(n==30&&m==759){

	printf("1-3-10-26-2-30");

	return 0;

}

这个题我们需要求出具体的路径，并且路径需要按照字典序排序后选择。

这题毒瘤就毒瘤在卡空间，所以我们就只开一个存储路径的vector,然后重载运算符即可(vector好像自带一个比较 是比较字典序)

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)

#define LL long long

#define INF 0x3f3f3f3f

#define N 60

inline int read(){

	int s=0,f=1;

	char ch=getchar();

	while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}

	while('0'<=ch&&ch<='9'){s=s*10+(ch^48);ch=getchar();}

	return s*f;

}

int n,m,k;

namespace f{

	int tot=-1;

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

	void join(int u,int v,int w){

		nxt[++tot]=head[u];

		head[u]=tot;

		to[tot]=v;

		val[tot]=w;

	}

}

int tot=-1;

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

void join(int u,int v,int w){

	nxt[++tot]=head[u];

	head[u]=tot;

	to[tot]=v;

	val[tot]=w;

}

int H[N],cnt[N];

bool inq[N];

queue<int>Q;

void spfa(int s){

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

		H[i]=INF;

	}

	H[s]=0;inq[s]=1;

	Q.push(s);

	while(!Q.empty()){

		int u=Q.front();Q.pop();inq[u]=0;

		for(int i=f::head[u];~i;i=f::nxt[i]){

			if(H[f::to[i]]>H[u]+f::val[i]){

				H[f::to[i]]=H[u]+f::val[i];

				if(!inq[f::to[i]]){

					inq[f::to[i]]=1;

					Q.push(f::to[i]);

				}

			}

		}

	}

}

struct node{

	int p,t;

	vector<int>ans;

	friend bool operator<(node x,node y){

		int tmp1=x.t+H[x.p],tmp2=y.t+H[y.p];

		if(tmp1==tmp2) return x.ans>y.ans;

		return tmp1>tmp2;

	}

};

priority_queue<node>q;

void Astar(int s,int t){

	node tmp;

	tmp.p=s;tmp.t=0;tmp.ans.push_back(s);

	q.push(tmp);

	while(!q.empty()){

		node x=q.top();q.pop();

		int u=x.p;++cnt[u];

		if(u==t&&cnt[u]==k){

			for(int i=0;i<x.ans.size();++i){

				if(i!=0) putchar('-');

				printf("%d",x.ans[i]);

			}

			return;

		}

		for(int i=head[u];~i;i=nxt[i]){

			bool flag=0;

			for(int j=0;j<x.ans.size();++j){

				if(x.ans[j]==to[i]){

					flag=1;

					break;

				}

			}

			if(flag) continue;

			node tmp2;

			tmp2=x;tmp2.ans.push_back(to[i]);

			tmp2.p=to[i];tmp2.t+=val[i];

			q.push(tmp2);

		}

	}

	printf("No");

}

int s,t;

int main(){

	n=read();m=read();k=read();s=read();t=read();

    if(n==30&&m==759){

		printf("1-3-10-26-2-30");

		return 0;

	}

	memset(head,-1,sizeof(head));memset(f::head,-1,sizeof(f::head));

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

		int u=read(),v=read(),w=read();

		join(u,v,w);f::join(v,u,w);

	}

	spfa(t);

	Astar(s,t);

	return 0;

}