求助dalao，此题A*怎么做

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define re register
#define isnum(x) (x<58&&x>47)
inline int read(){
	int ans=0,v=1;
	char ch=getchar();
	while(!isnum(ch)&&ch^45)ch=getchar();
	if(!(ch^45))v=-1,ch=getchar();
	while(isnum(ch))ans=(ans<<1)+(ans<<3)+ch-48,ch=getchar();
	return ans*v;
}
const int maxn=100001;
const int maxm=200001;
const int INF=2147383467;
struct edge{
	int nxt,to,w;
}E[maxm];
int n,m,k,P;
int cnt,ans;
int x[maxm],y[maxm],z[maxm];
int head[maxn],dis[maxn],vis[maxn];
inline void add(int u,int v,int w){
	cnt++;
	E[cnt].to=v;
	E[cnt].nxt=head[u];
	E[cnt].w=w;
	head[u]=cnt;
}
inline void dijkstra(){
	for(re int i=1;i<=n;i++)
		dis[i]=INF;
	dis[n]=0;
//	vis[n]=1;
	queue<int>q;
	q.push(n);
	while(!q.empty()){
		int v=q.front();
		q.pop();
		//printf("%d\n",v);
		for(re int i=head[v];i;i=E[i].nxt){
			int u=E[i].to,d=E[i].w;
			if(dis[u]>dis[v]+d){
				dis[u]=dis[v]+d;
				//printf("%d %d\n",u,dis[u]);
			//	if(!vis[u]){
			//		vis[u]=1;
					q.push(u);		
			//	}
			}
		}
	}
}
struct node{
	int to,f,g;
	bool operator <(const node a) const {
		if(a.f^f)return f>a.f;
		return g>a.g;
	}
};
inline void A_star(){
	node temp;
	temp.to=1;
	temp.g=0;
	temp.f=dis[1];
	priority_queue<node>q;
	q.push(temp);
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		int u=tmp.to;
	//	printf("%d\n",u);
		if(!(u^n)){
			ans++;
			ans%=P;
			printf("%d\n",ans);
			if(dis[1]+k<tmp.g)return ;
		}
		for(re int i=head[u];i;i=E[i].nxt){
	//		printf("%d\n",E[i].to);
			
			temp.to=E[i].to;
			temp.g=tmp.g+E[i].w;
			temp.f=temp.g+dis[temp.to];
			q.push(temp);
		}
	//	getchar();
	}
}
int T;
int main(){
	freopen("f:/testdata.in","r",stdin);
	T=read();
	while(T--){
		ans=0;
		cnt=0;
		memset(head,0,maxn<<2);
		n=read();m=read();k=read();P=read();
		for(re int i=1;i<=m;i++){
			int u=read(),v=read(),w=read();
			add(v,u,w);
			x[i]=u;y[i]=v;z[i]=w;
		}
		for(re int i=1;i<=m;i++){
		//	int v=0;
			if(!z[i])
				for(re int j=y[i];!z[j];j=y[j]){
					if(!(x[i]^x[j])){
						puts("-1");
					break;
					
				}
			}
		}
		dijkstra();
	/*	for(re int i=1;i<=n;i++)
		printf("%d %d\n",i,dis[i]);*/
		cnt=0;
		memset(head,0,maxn<<2);
		for(re int i=1;i<=m;i++){
			add(x[i],y[i],z[i]);
		}
		A_star();
		printf("%d\n",ans-1);
	}
	fclose(stdin);
	return 0;
}