记录编号	176935	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.155 s
提交时间	2015-08-10 14:46:35	内存使用	1.75 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=10000+100;
const int inf=0x7fffffff/3;
struct edge{
	int next,to,w;
}G[maxn*10];
int h[maxn],q[maxn*10],dis[maxn],tot=0,n,m,k;
bool vis[maxn];
struct data{//g 表示起点到当前点的距离，h表终点到当前点的距离
    int g,h,to;
    bool operator < (data a)const{//优先队列的排序（其实也不能这么讲） 使g+h小的在队首
        return a.h+a.g<h+g;
    }
};
priority_queue<data>Q;

void add(int x,int y,int z){
	++tot; G[tot].to=y; G[tot].w=z;
	G[tot].next=h[x]; h[x]=tot;
}

void spfa(int x){
	q[1]=x; vis[x]=1;
	for (int i=1;i<=n;++i) dis[i]=inf;
	dis[x]=0;
	int head=1,t=1,now;
	while (head<=t){
		now=q[head]; head++; vis[now]=0;
		for (int i=h[now];i;i=G[i].next)
		   if (dis[G[i].to]>dis[now]+G[i].w){
				dis[G[i].to]=dis[now]+G[i].w;
				if (!vis[G[i].to]){
					q[++t]=G[i].to;
					vis[G[i].to]=1;
				}
		   }
	}
}

int Astar(){
	int cnt[maxn]={0};
	data cur,nxt; 
	cur.to=1; cur.g=0; cur.h=dis[1];
	Q.push(cur);
	while (!Q.empty()){
		cur=Q.top(); Q.pop(); cnt[cur.to]++;
		if (cnt[cur.to]>k) continue;
		if (cnt[n]==k) return cur.g;
		for (int i=h[cur.to];i;i=G[i].next){
			nxt.to=G[i].to;
			nxt.g=cur.g+G[i].w;
			nxt.h=dis[G[i].to];
			Q.push(nxt);
		}
	}
	return -1;
}

int main()
{
	freopen("dota.in","r",stdin);
	freopen("dota.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,z;
	for (int i=1;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z); add(y,x,z);
	}
	int flag; scanf("%d",&flag);
	if (flag==0) {spfa(1); printf("%d",dis[n]);return 0;}
	spfa(n); k=2; int ans=Astar(); printf("%d",ans);
	return 0;
}