#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 10010
#define M 1000100
#define QM 5000010
int n,m;
int st,ed,k;
struct arr{
	int ff,tt,ww,next;
}c1[M],c[M];
int r1[M],r[M];
int tot1 = 0,tot = 0;
int dis[N],d[N];
bool v[N];
struct ar{
	struct data{
		int xx,ww;
	}h[QM];
	int s;
	void clean(){
		memset(h,0,sizeof(h));
		s = 0;
	}
	
	void up(int x){
		int p = x >> 1;
		while (p){
			if (h[p].ww > h[x].ww) swap(h[p],h[x]);
			else return;
			x = p;
			p = x >> 1;
		}
		return;
	}
	
	void push(int x,int w){
		h[++s].xx = x;
		h[s].ww = w;
		if (s == 1) return;
		up(s);
	}
	
	void down(int x){
		int p = x << 1;
		while (p <= s){
			if (h[p].ww > h[p + 1].ww && p < s) p++;
			if (h[p].ww < h[x].ww) swap(h[p],h[x]);
			else return;
			x = p;
			p = x << 1;
		}
	}
	
	int size(){
		return s;
	}
	data top(){
		return h[1];
	}
	
	void pop(){
		h[1] = h[s --];
		if (!s) return;
		down(1);
	}
	
}Q;
struct arrr{
	struct data{
		int xx,ww;
	}h[QM];
	int s;
	void clean(){
		memset(h,0,sizeof(h));
		s = 0;
	}
	
	void up(int x){
		int p = x >> 1;
		while (p){
			if (h[p].ww + dis[h[p].xx]> dis[h[x].xx]+h[x].ww) swap(h[p],h[x]);
			else return;
			x = p;
			p = x >> 1;
		}
		return;
	}
	
	void push(int x,int w){
		h[++s].xx = x;
		h[s].ww = w;
		if (s == 1) return;
		up(s);
	}
	
	void down(int x){
		int p = x << 1;
		while (p <= s){
			if (h[p].ww + dis[h[p].xx]> h[p + 1].ww + dis[h[p + 1].xx] && p < s) p++;
			if (h[p].ww + dis[h[p].xx]< h[x].ww + dis[h[x].xx]) swap(h[p],h[x]);
			else return;
			x = p;
			p = x << 1;
		}
	}
	
	int size(){
		return s;
	}
	data top(){
		return h[1];
	}
	
	void pop(){
		h[1] = h[s --];
		if (!s) return;
		down(1);
	}
	
}QQ;

inline void add(int x,int y,int z){
	c[++tot].ff = x;
	c[tot].tt = y;
	c[tot].ww = z;
	c[tot].next = r[x];
	r[x] = tot;
	return ;
}

inline void add1(int x,int y,int z){
	c1[++tot1].ff = x;
	c1[tot1].tt = y;
	c1[tot1].ww = z;
	c1[tot1].next = r1[x];
	r1[x] = tot1;
	return;
}

inline int getint(){
	char ch;
	int x = 0;
	while (!isdigit(ch = getchar()));
	x = ch - 48;
	while (isdigit(ch = getchar())) x = x * 10 + ch - 48;
	return x;
}

void heap_dijsktra(){
	memset(dis,0x3f,sizeof(dis));
	memset(v,0,sizeof(v));
	dis[ed] = 0;
	Q.clean();
	Q.push(ed,0);
	while (Q.size()){
		int x = Q.top().xx;
		Q.pop();
		if (v[x])continue;
		v[x] = 1;	
		for (int i = r1[x]; i; i = c1[i].next){
			int y = c1[i].tt;
			if (dis[y] > dis[x] + c1[i].ww){
				dis[y] = dis[x] + c1[i].ww;
				Q.push(y,dis[y]);
			}
		}
	}
	return;
}
int ans;

void A_star(){
	QQ.clean();
	QQ.push(st,0);
	while (d[ed] < k && QQ.size()){
		int x = QQ.top().xx;
		d[x]++;
		if (d[ed] == k) {
			ans = QQ.top().ww;
			return;
		}
		if (d[x] <= k){
			for (int i = r[x]; i ; i = c[i].next){
				QQ.push(c[i].tt,c[i].ww + QQ.top().ww);
			}
		}
		QQ.pop();
	}
	return;
}

int main(){
	n = getint();
	m = getint();
	int x,y,z;
	for (int i = 1; i <= n; i++){
		x = getint(); y = getint();
		z = getint();
		add(x,y,z);
		add1(y,x,z);
	}
	st = getint();ed = getint();k = getint();
	if (st == ed) k++;
	heap_dijsktra();
	A_star();
	if (d[ed] == k) printf("%d\n",ans);
	else puts("-1");
	return 0;
}

• Re:谁能告诉我我的A*为甚么超时?看出来的mail我，谢谢 (3858) JJW1231 2016-08-26 20:32:35