T105289 【模板】A*

题目地址

---

注意点：

• 起点和终点相同时，k需要提前++.
• Node内的比较函数应当使用:当前费用+预估费用.

---

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=3e3,MAXM=3e5;
struct Edge_First{//反向图 
	int from,to,nxt,w;
}e_First[MAXM];
int head_First[MAXN],edgeCnt_First=1;
void addEdge_First(int u,int v,int w){
	e_First[++edgeCnt_First].from=u;
	e_First[edgeCnt_First].to=v;
	e_First[edgeCnt_First].w=w;
	e_First[edgeCnt_First].nxt=head_First[u];
	head_First[u]=edgeCnt_First;
}
int s,t,k;//起点 终点 第k短路 
struct Node_First{
	int v,dis;
	bool operator <(Node_First another)const{
		return dis>another.dis;
	}
};
int f[MAXN];//估价函数 
void dijkstra(){
	memset(f,0x3f,sizeof(f));
	priority_queue<Node_First> q;
	q.push(Node_First{t,0});
	f[t]=0;
	while(!q.empty()){
		Node_First nowNode=q.top();
		q.pop();
		int nowU=nowNode.v;
		if(nowNode.dis!=f[nowU])continue;
		for(int i=head_First[nowU];i;i=e_First[i].nxt){
			int nowV=e_First[i].to;
			if(f[nowV]>f[nowU]+e_First[i].w){
				f[nowV]=f[nowU]+e_First[i].w;
				q.push(Node_First{nowV,f[nowV]});
			}
		}
	}
}
struct Edge{
	int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v,int w){
	e[++edgeCnt].from=u;
	e[edgeCnt].to=v;
	e[edgeCnt].w=w;
	e[edgeCnt].nxt=head[u];
	head[u]=edgeCnt;
}
struct Node{
	int v,f,g; 
	bool operator <(Node another)const{
		return f+g>another.f+another.g;
	}
};
int updateTime[MAXN];
int ans;
bool Astar(){
	priority_queue<Node> q;
	q.push(Node{s,f[s],0});
	while(!q.empty()){
		Node nowNode=q.top();
		q.pop();
		int nowU=nowNode.v;
		updateTime[nowU]++;
		if(nowU==t&&updateTime[nowU]==k){
			ans=nowNode.g;
			return 1;
		}
		for(int i=head[nowU];i;i=e[i].nxt){
			int nowV=e[i].to;
			q.push(Node{nowV,f[nowV],nowNode.g+e[i].w});
		}
	}
	return 0;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b,l;
		scanf("%d%d%d",&a,&b,&l);
		addEdge_First(b,a,l);//反向边
		addEdge(a,b,l);//正向边 
	}
	scanf("%d%d%d",&s,&t,&k);
	if(s==t)k++;
	dijkstra();
	if(Astar()){
		cout<<ans<<endl;
	}else cout<<"-1"<<endl;
	return 0;
}