Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:谁能告诉我我的A*为甚么超时?看出来的mail我，谢谢

Posted by JJW1231 at 2016-08-26 20:32:35 on Problem 2449
In Reply To:谁能告诉我我的A*为甚么超时?看出来的mail我，谢谢 Posted by:hzoi_hexing at 2014-04-17 21:33:59
```> #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();
> 	}
> 	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;
> }
```

Followed by: