记录编号	270319	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.089 s
提交时间	2016-06-14 18:54:10	内存使用	2.22 MiB

#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=100000;
const int maxe=150050;
struct Edge {
	int dis,to,next;
}e[maxn];
struct Node{
	int num,dis,g,h;
	Node(){};
	Node(int a,int b){num=a;dis=b;}
	Node(int a,int b,int c){num=a;g=b;h=c;dis=g+h;}
	bool operator <(const Node & a)const {
		return dis>a.dis;
	}
};
int len,head[maxn],dis[maxn],n,m;
void Insert(int,int,int);
void Astar();
void Dijs(int);
void Init();
int main(){
	freopen("dota.in","r",stdin);
	freopen("dota.out","w",stdout);
	Init();
	return 0;
}
void Init(){
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		Insert(x,y,z);
		Insert(y,x,z);
	}
	Dijs(n);
	int type;
	scanf("%d",&type);
	if(type==0){
		printf("%d\n",dis[1]);return;
	}
	Astar();
}
void Insert(int x,int y,int z){
	len++;
	e[len].to=y;
	e[len].next=head[x];
	e[len].dis=z;
	head[x]=len;
}
void Dijs(int x){
	memset(dis,0x7f,sizeof(dis));dis[x]=0;
	bool f[maxn];memset(f,0,sizeof(f));f[x]=1;
	priority_queue<Node> q;
	q.push(Node(x,dis[x]));
	while(!q.empty()){
		Node temp=q.top();q.pop();
		int k=temp.num;f[k]=1;
		for(int i=head[k];i!=-1;i=e[i].next){
			int j=e[i].to;
			if(!f[j] && dis[j]>dis[k]+e[i].dis){
				dis[j]=dis[k]+e[i].dis;
				q.push(Node(j,dis[j]));
			}
		}
	}
}
void Astar(){
	bool flag=0;
	priority_queue<Node> q;
	q.push(Node(1,0,dis[1]));
	while(!q.empty()){
		Node temp=q.top();q.pop();
		if(temp.num==n){
			if(flag==1){
				printf("%d\n",temp.g);
				return;
			}
			else flag=1;
		}
		for(int i=head[temp.num];i!=-1;i=e[i].next){
			q.push(Node(e[i].to,e[i].dis+temp.g,dis[e[i].to]));
		}
	}
}