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

边集数组...开到200200 就正好= =大小要么RE 要么TLE

Posted by dong_123 at 2013-03-14 16:03:16 on Problem 2449
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define inf 2000000000
#define maxn 1005
#define maxm 100100
using namespace std;
typedef struct{
	int y,next,w;
}node;
struct data{
	int v,d,h;
	 bool operator <( data a )const  
       {    return a.d+a.h<d+h;   }  
};
node g[maxm*2];
int m,n,tot=0,kth,s,t;
int d[maxn],a[maxn],time[maxn],v[maxn],b[maxn];
void Add(int x,int y,int z){
	g[++tot].y=y;g[tot].w=z;g[tot].next=a[x];a[x]=tot;
	g[++tot].y=x;g[tot].w=z;g[tot].next=b[y];b[y]=tot;
}
void Init(){
	int x,y,z;
	freopen("test.in","r",stdin);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&z);
		Add(x,y,z);
		//Add(y,x,z);
	}
	scanf("%d %d %d",&s,&t,&kth);
	if(s==t) kth++;
}
void Dij(){
	int mind,mini,now;
	for(int i=1;i<=n;i++) d[i]=inf;
	memset(v,0,sizeof(v));
	d[t]=0;
	for(int i=1;i<=n;i++){
		mind=inf;
		for(int j=1;j<=n;j++)
			if(!v[j]&&mind>d[j]){
				mind=d[j];
				mini=j;
			}
		v[mini]=1;
		for(int s=b[mini];s;s=g[s].next){
			now=g[s].y;
			if(!v[now]&&d[now]>d[mini]+g[s].w){
				d[now]=d[mini]+g[s].w;
			}
		}
	}
	//for(int i=1;i<=n;i++) printf("%d\n",d[i]);
}
int A_Star(){
	data st,now,k;
	priority_queue<data>que;
	memset(time,0,sizeof(time));
	st.v=s;
	st.d=0;
	st.h=d[s];
	que.push(st);
	while(!que.empty()){
		k=que.top();
		que.pop();
		if(++time[k.v]>kth) continue;
		if(time[t]==kth) return(k.d);
		for(int s=a[k.v];s;s=g[s].next){
			now.v=g[s].y;
			now.d=k.d+g[s].w;
			now.h=d[g[s].y];
			que.push(now);
		}
	}
	return(-1);
}
int main(){
	Init();
	Dij();
	printf("%d\n",A_Star());
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator