记录编号	321482	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.157 s
提交时间	2016-10-13 19:24:51	内存使用	4.60 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100010,maxe=150010;
struct edge{
	int to,dis;
	edge* prev;
	edge():to(0),dis(0x7ffffff),prev(NULL){}
}ee[maxe<<1];
struct node{
	int num,g,h;
	node(){}
	node(int num,int g,int h=0):num(num),g(g),h(h){}
	bool operator<(const node& x)const{
		return g+h>x.g+x.h;
	}
};
void insert(int,int,int);
void dijkstra(int);
int Astar(int,int);
int len=0;
edge* last[maxn]={NULL};
bool vis[maxn];
int dis[maxn];
int n,m,s,t,x,y,z,p;
int main(){
#define MINE
#ifdef MINE
	freopen("dota.in","r",stdin);
	freopen("dota.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&x,&y,&z);
		insert(x,y,z);
		insert(y,x,z);
	}
	scanf("%d",&p);
	dijkstra(n);
	if(p)printf("%d",Astar(1,n));
	else printf("%d",dis[1]);
	return 0;
}
void insert(int x,int y,int z){
	ee[len].to=y;
	ee[len].prev=last[x];
	ee[len].dis=z;
	last[x]=&ee[len++];
}
void dijkstra(int x){
	int y;
	memset(vis,0,sizeof(vis));
	memset(dis,63,sizeof(dis));
	priority_queue<node>heap;
	heap.push(node(x,0));
	while(!heap.empty()){
		node b=heap.top();
		heap.pop();
		x=b.num;
		if(vis[x])continue;
		vis[x]=true;
		dis[x]=b.g;
		for(edge* e=last[x];e;e=e->prev){
			y=e->to;
			heap.push(node(y,b.g+e->dis));
		}
	}
}
int Astar(int s,int t){
	int x,y;
	priority_queue<node>heap;
	heap.push(node(s,0,dis[s]));
	while(!heap.empty()){
		node b=heap.top();
		heap.pop();
		x=b.num;
		if(x==t&&b.g!=dis[s])return b.g;
		for(edge* e=last[x];e;e=e->prev){
			y=e->to;
			heap.push(node(y,b.g+e->dis,dis[y]));
		}
	}
	return -1;
}