#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<malloc.h>
#include<string.h>
#include<limits.h>
#define VERTEX_NUM 1000000
struct AVL_Node *AVL_Tree;
struct Vertex{
	char name[100];
	int d; //出発点からの距離
	int is_visited;
	struct Edgelist *edge_head;
	struct Vertex *shortest_path;
};
struct Edgelist {
	int length; //辺の長さ
	struct Vertex *to;
	struct Edgelist *next;
};


int Max(int lh, int rh){
	int Max;
	Max = lh;
	if(lh <= rh)Max = rh;
	return Max;
}

void initialize_vertex(struct Vertex *v, char *name){
	strcpy(v->name,name);
	v->d=INT_MAX/2; //int型の最大値
	v->edge_head=NULL;
	v->shortest_path=NULL;
	v->is_visited=0;
}
void connect_dir(struct Vertex *from, struct Vertex *to, int length){
	struct Edgelist *new_edge;
	new_edge=(struct Edgelist *)malloc(sizeof(struct Edgelist));
	new_edge->to = to;
	new_edge->next= from->edge_head;
	from->edge_head=new_edge;
	new_edge->length=length;
}
struct AVL_Node{
	struct Vertex *v; // 頂点をおぼえる
	struct AVL_Node *left;
	struct AVL_Node *right;
	int h;
};
struct AVL_Node* new_AVL_Node(struct Vertex *v){
	struct AVL_Node *n;
	n=(struct AVL_Node*)malloc(sizeof(struct AVL_Node));
	n->v=v;
	n->h=0; n->left=NULL; n->right=NULL;
	return n;
}
struct AVL_Node *new_AVL_Node(struct Vertex *v);
struct AVL_Node *insert_v(struct AVL_Node *p, struct Vertex *v);
struct AVL_Node *insert_n(struct AVL_Node *p, struct AVL_Node*x);
struct AVL_Node *rotate(struct AVL_Node *p);
int compare_vertex(struct Vertex *a, struct Vertex *b);
void set_height(struct AVL_Node *p);
struct AVL_Node *find_min(struct AVL_Node *T_root);
struct AVL_Node *remove_min(struct AVL_Node *T_root);
struct AVL_Node *delete_v(struct AVL_Node *T_root, struct Vertex *v);
int compare_vertex(struct Vertex *a, struct Vertex *b){
	if(a->d< b->d){
		return -1;
	} else if( a->d > b->d){
		return 1;
	} else {
		return strcmp(a->name,b->name);
	}
}

void set_height(struct AVL_Node *p){
	if(p==NULL){
		return ;
	} else if(p->left==NULL && p->right==NULL){
		p->h=0;
	} else if(p->left==NULL && p->right!=NULL){
		p->h=p->right->h+1;
	} else if(p->left!=NULL && p->right==NULL){
		p->h=p->left->h+1;
	} else {
		p->h=Max(p->left->h,p->right->h)+1;
	}
}
//*関数maxは自分で作る*//
struct AVL_Node *
insert_n(struct AVL_Node *p, struct AVL_Node *x){
	if(x==NULL){ return p; }
	if(compare_vertex(x->v,p->v)<0){
		if(p->left==NULL){ p->left=x; }
		else { p->left = insert_n(p->left, x); }
	} else if(compare_vertex(x->v,p->v)>0){
		if(p->right==NULL){ p->right=x; }
		else { p->right = insert_n(p->right,x); }
	} else{
		return p;
	}
	set_height(p);
	return rotate(p); /* 回転による根の入替に対応*/
}

struct AVL_Node* insert_v(struct AVL_Node *p, struct Vertex *v){
	struct AVL_Node *n= new_AVL_Node(v);
	if(p!=NULL){ return insert_n(p,n); }
	else { return n; }
}

struct AVL_Node* rotate(struct AVL_Node *p){
	int lh=-1, rh=-1, llh=-1,lrh=-1, rlh=-1,rrh=-1;
	if(p==NULL)return NULL;
	if(p->left!=NULL){
		lh=p->left->h;
		if(p->left->left!=NULL){ llh=p->left->left->h;}
		if(p->left->right!=NULL){lrh=p->left->right->h;}
	}
	if(p->right!=NULL){
		rh=p->right->h;
		if(p->right->left!=NULL){ rlh=p->right->left->h;}
		if(p->right->right!=NULL){ rrh=p->right->right->h;}
	}
	if(lh-rh<=1 && rh-lh<=1){ return p; }
	if(lh < rh){ /* 右の子が高い*/
		struct AVL_Node *A=p, *B=p->right;
		struct AVL_Node *Y=B->left;
		if(rlh<rrh){ /*右の右の孫が高い：１重回転*/
			B->left=A; A->right=Y;
			set_height(A); set_height(B);
			return B;
		} else {/*右の左の孫が高い：２重回転 */
			struct AVL_Node *C=Y, *Y1=C->left, *Y2=C->right;
			C->left=A; C->right=B; A->right=Y1; B->left=Y2;
			set_height(A); set_height(B); set_height(C);
			return C;
		}
	}else { /*左の子が高い*/
		struct AVL_Node *A=p, *B=p->left;
		struct AVL_Node *Y=B->right;
		if(llh > lrh){/* 左の左の孫が高い：１重回転*/
			B->right=A; A->left=Y;
			set_height(A); set_height(B);
			return B;
		} else {/*左の右の孫が高い：２重回転*/
			struct AVL_Node *C=Y, *Y1=C->left, *Y2=C->right;
			C->left=B; C->right=A; B->right= Y1; A->left=Y2;
			set_height(A); set_height(B); set_height(C);
			return C;
		}
	}
}


struct AVL_Node *find_min(struct AVL_Node *p){
	struct AVL_Node *q;
	if(p==NULL){
		return NULL;
	}
	for(q=p;q->left!=NULL;q=q->left){
		; /* なにもしない*/
	}
	/* qに左の子が存在しないのでqは最小値 */
	return q;
}

struct AVL_Node *remove_min(struct AVL_Node *p){
	if(p==NULL){
		return NULL;
	} else if(p->left==NULL) {
		return p->right;
	} else if(p->left->left==NULL){
		/*左の左の孫が無いならば、pは最小値の親*/
		p->left=p->left->right;
		set_height(p);
		return rotate(p);
	} else {
		p->left=remove_min(p->left);
		set_height(p);
		return rotate(p);
	}
}

struct AVL_Node *delete_v(struct AVL_Node *p, struct Vertex *v){
	struct AVL_Node *min_node;
	if(p==NULL || v==NULL){
		return NULL;
	}
	if(compare_vertex(v,p->v)<0){
		p->left=delete_v(p->left,v);
		set_height(p);
		return rotate(p);
	} else if(compare_vertex(v,p->v)>0){
		p->right=delete_v(p->right,v);
		set_height(p);
		return rotate(p);
	}

	if(p->right==NULL){
		struct AVL_Node *left= p->left;
		free(p);
		return rotate(left);
	} else {
		min_node=find_min(p->right);
		p->right=remove_min(p->right);
		min_node->left=p->left;
		min_node->right=p->right;
		free(p);
		set_height(min_node);
		return rotate(min_node);

}}

void read_file(char *filepath,struct Vertex vertex[]){
	FILE *fp;
	fp=fopen(filepath,"rt");
	if(fp==NULL){
		printf("ファイルオープン失敗\n%s\n",filepath); return;
	}
	while(!feof(fp)){
		char buf[1000]; int from, to, length;
		fgets(buf,1000,fp);
		if(buf[0]!='a') continue;
		sscanf(buf,"%c %d %d %d",&buf[0], &from, &to, &length);
		connect_dir(&vertex[from],&vertex[to],length);
	}
	fclose(fp);
}

struct Vertex* extract_nearest_AVL();
void add_all_vertices_to_AVL_Tree(struct Vertex *s);
void Dijkstra_fast(struct Vertex *s);


void add_all_vertices_to_AVL_Tree(struct Vertex *s){
	struct Edgelist *e;
	s->is_visited=1;
	AVL_Tree=insert_v(AVL_Tree,s);
	for(e=s->edge_head; e!=NULL; e=e->next){
		if(e->to->is_visited==0){
			add_all_vertices_to_AVL_Tree(e->to);
		}
	}
	return;
}

struct Vertex* extract_nearest_AVL(){
	struct AVL_Node *min_node;
	struct Vertex *min_vertex;

	min_node=find_min(AVL_Tree);
	min_vertex=min_node->v;
	AVL_Tree=delete_v(AVL_Tree,min_vertex); return min_vertex;
}

void Dijkstra_fast(struct Vertex *s){
	struct Edgelist *e; struct Vertex *u;
	s->d=0;
	add_all_vertices_to_AVL_Tree(s);
	while(AVL_Tree!=NULL){
		u=extract_nearest_AVL();
		for( e= u->edge_head; e!=NULL; e=e->next){
			if(e->to->d > u->d + e->length){
				AVL_Tree=delete_v(AVL_Tree,e->to);
				e->to->d=u->d+e->length;
				e->to->shortest_path=u;
				AVL_Tree=insert_v(AVL_Tree,e->to);
			}
		}
	}
}

int main(void ){
	struct Vertex *p;
	char filename[]="USA-road-d.NY.gr";
	int i,j;
	time_t start,end;
	struct Vertex *vertex_array=
	(struct Vertex *)malloc(sizeof(struct Vertex)*VERTEX_NUM);
	printf("初期化中...");
	for(i=0;i<VERTEX_NUM;i++){
		char name[100];
		sprintf(name,"V%d",i);
		initialize_vertex(&vertex_array[i],name);
	}
	printf("初期化完了\n");
	printf("地図読み込み中...");

	read_file(filename,vertex_array);
	printf("地図読み込み完了\n");

	AVL_Tree=NULL;
	start=clock();
	Dijkstra_fast(&vertex_array[999]);
	end=clock();
	for(p=&vertex_array[9999];p!=NULL;p=p->shortest_path){
		printf("%s<-- ", p->name);
	}
	printf("最短路の長さは%d\n", vertex_array[9999].d);
	printf("%5.4f秒でした\n",(end-start)/(double)CLOCKS_PER_SEC);
	getchar(); return 0;


}