记录编号	248151	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.085 s
提交时间	2016-04-10 08:18:11	内存使用	4.03 MiB

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#define MAX_NODE 10010
#define MAX_LENS 200100
char c;
inline void read(int &k){k=0;
	do{c=getchar();}while(c<'0'||c>'9');
	do{k=k*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
}
struct Path{
	int to;
	int dis;
	int next;
	Path(){to=-1;dis=0x7ffffff;next=-1;}
};
struct Picture{
	int from,to,dis;
}PIC[MAX_LENS];
struct Node{
	long long int f;
	int g;
	int place;
	Node(long long int a=0,int b=0,int c=0):f(a),g(b),place(c){}
	bool operator < (const Node &a)const{
		return f<a.f;
	}
};
struct Heap{
	int size;
	Node table[MAX_LENS];
	Heap(){size=0;}
	void exchange(Node &a,Node &b){
		Node c=a;a=b;b=c;
	}
	bool empty(){return size==0;}
	void push(const Node &number){
		int place=size;
		int last;
		table[size]=number;
		size++;
		while(place!=0){
			last=(place-1)>>1;
			if(table[place]<table[last])exchange(table[last],table[place]);
			else break;
			place=last;
		}
	}
	Node pop(){
		Node ans=table[0];
		table[0]=table[--size];
		int t=0;
		int l=1,r=2;
		while(l<size)
		{
			if(r<size&&table[r]<table[l])l=r;
			if(table[l]<table[t]){exchange(table[t],table[l]);t=l;}
			else break;
			l=(t<<1|1);r=(t<<1)+2;
		}
		return ans;
	}
};
struct Pic{
	int lens;
	int points;
	int len_num;
	int cnt[MAX_NODE];
	int dis[MAX_NODE];
	int head[MAX_NODE];
	Path table[MAX_LENS];
	Heap q;
	Pic(){lens=0;memset(dis,40,sizeof(dis));memset(head,-1,sizeof(head));doing();}
	void clean(){
		lens=0;memset(head,-1,sizeof(head));memset(table,-1,sizeof(table));
	}
	void add(const bool &flag=1){
		if(flag==1){
			for(int i=1;i<=len_num;++i){
				table[++lens].next=head[PIC[i].from];
				table[lens].to=PIC[i].to;
				table[lens].dis=PIC[i].dis;
				head[PIC[i].from]=lens;
			}
		}
		else{
			for(int i=1;i<=len_num;++i){
				table[++lens].next=head[PIC[i].to];
				table[lens].to=PIC[i].from;
				table[lens].dis=PIC[i].dis;
				head[PIC[i].to]=lens;
			}
		}
	}
	void dijsa(int from){
		dis[from]=0;
		q.push(Node(0,0,from));
		while(!q.empty()){
			Node ppt=q.pop();
			if(dis[ppt.place]!=ppt.f)continue;
			for(int i=head[ppt.place];i!=-1;i=table[i].next){
				if(dis[table[i].to]>dis[ppt.place]+table[i].dis){
					dis[table[i].to]=dis[ppt.place]+table[i].dis;
					q.push(Node(dis[table[i].to],0,table[i].to));
				}
				//printf("000>>>%d<<<\n",q.size);
			}	
		}
	}
	
	void A_Star(int from,int to,int Times){
		if(from==to)++Times;
		while(!q.empty())q.pop();
		q.push(Node(dis[from],0,from));
		while(!q.empty()){
			Node pos=q.pop();
			if(pos.place==to){
				--Times;
				if(Times==0){
					std::cout<<pos.g;
					return ;
				}
			}
			for(int i=head[pos.place];i!=-1;i=table[i].next){
				q.push(Node( dis[table[i].to]+table[i].dis+pos.g, table[i].dis+pos.g ,table[i].to));
				//printf(">>>>%d\n",q.size);
			}
		}
		puts("-1");
		return;
	}
	int doing(){
		freopen("dota.in","r",stdin);
		freopen("dota.out","w",stdout);
		read(points);
		read(len_num);
		int a,b,c,from,to,Times; 
		for(int i=1;i<=len_num;++i){
			read(a);read(b);read(c);
			PIC[i].from=a;
			PIC[i].to=b;
			PIC[i].dis=c;
		}
		int p;
		read(p);
		if(!p){
			add(0);add(1);dijsa(points);
			printf("%d",dis[1]);
		}else {
			add(0);add(1);dijsa(points);
			A_Star(1,points,2);
		}
		return 0;
	}
}a;
int main(){;}