学步园

#include<cstring>
#include<cstdio>
#include<climits>
#include<queue>
#include<algorithm>
using namespace std;

#define N 1005
#define maxn 290100

int m,n,Next[N],Tail[N],start,des,k,cnt = 0;
int d[N];

struct Node
{
	int to,next,lens;
};
Node node[maxn];

struct Temp
{
	int g,h,lens,to;			// g = g+d[to];to为当前到达的节点，这里就是f = g+h；
	bool operator<(Temp a)const{ //不知道为啥，这里这样写就不会mle
		return a.h + a.g < h + g;
	}
};

void add_edge(int a,int b,int c)
{
	node[cnt].to = b,node[cnt].lens = c;
	node[cnt].next = Next[a],Next[a] = cnt++;
	swap(a, b);
	node[cnt].to = b,node[cnt].lens = c;
	node[cnt].next = Tail[a],Tail[a] = cnt++;
}

void spfa()
{
	bool vis[N];
	memset(vis, false, sizeof(vis));
	fill(d, d+n+1, INT_MAX);
	d[des] = 0;
	queue<int> q;
	q.push(des);
	while( !q.empty() )
	{
		int x = q.front();q.pop();
		vis[x] = false;
		for(int i = Tail[x]; i != -1; i = node[i].next){
			int v = node[i].to;
			if(d[v] > d[x] + node[i].lens)
			{
				d[v] = d[x] + node[i].lens;
				if(!vis[v])
					q.push(v),vis[v] = true;
			}
		}
	}
}

int Astar()
{
	int cou[N];
	Temp cur,next;
	priority_queue<Temp> q;
	memset(cou, 0, sizeof(cou));
	cur.g = 0,cur.to = start,cur.lens = d[start];
	q.push(cur);
	while(!q.empty())
	{
		cur = q.top();
		q.pop();
		cou[cur.to]++;
		if(cou[cur.to] > k)continue;
		if(cou[des] == k)return cur.g;
		for(int u = Next[cur.to]; u != -1; u=node[u].next)
		{
			int v = node[u].to;
			next.to = v;
			next.g = cur.g + node[u].lens;
			next.h = d[v];
			q.push(next);
		}
	}
	return -1;
}

int main()
{
	scanf("%d%d",&n,&m);
	memset(Tail,-1,sizeof(Tail));
	memset(Next,-1,sizeof(Next));
	while( m-- ){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add_edge(a,b,c);
	}
	scanf("%d%d%d",&start,&des,&k);
	if(start == des) k++;
	spfa();
	printf("%d\n",Astar());
}