记录编号	133462	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	Foenix	是否通过	通过
代码语言	C++	运行时间	0.076 s
提交时间	2014-10-28 06:13:46	内存使用	1.63 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map>
#include <queue>
using namespace std;
const int MAXN=50005;
struct Edge1{
	int to;
	int next;
	int va;
}A[MAXN<<1];
struct NODE{
	int to;
	int f,g;
	bool operator <(const NODE &X)const{
		if(f==X.f)return g>X.g;
		return f>X.f;
	}
};
int len1,len2;
int head1[20005];
void Build(int a,int b,int c){
	len1++;
	A[len1].to=b;
	A[len1].va=c;
	A[len1].next=head1[a];
	head1[a]=len1;
}
int n,m,p;
bool exist[20005];
int dis[20005];
void init(){
	scanf("%d%d",&n,&m);
	int a,b,c;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		Build(a,b,c);
		Build(b,a,c);
	}
	scanf("%d",&p);
}
void SPFA(){
	memset(dis,67,sizeof(dis));
	queue<int>T;
	T.push(n);
	exist[n]=true;
	dis[n]=0;
	int tmp,y;
	while(!T.empty()){
		tmp=T.front();
		T.pop();
		exist[tmp]=false;
		for(int i=head1[tmp];i;i=A[i].next){
			y=A[i].to;
			if(dis[y]>dis[tmp]+A[i].va){
				dis[y]=dis[tmp]+A[i].va;
				if(exist[y]==false){
					exist[y]=true;
					T.push(y);
				}
			}
		}
	}
}
int A_star(int st,int en,int k){
	int cnt=0;
	if(st==en)k++;
	NODE e,ne;
	priority_queue<NODE>T;
	e.to=st;
	e.g=0;
	e.f=e.g+dis[e.to];
	T.push(e);
	while(!T.empty()){
		e=T.top();
		T.pop();
		if(e.to==en)cnt++;
		if(cnt==k)return e.g;
		for(int i=head1[e.to];i;i=A[i].next){
			ne.to=A[i].to;
			ne.g=e.g+A[i].va;
			ne.f=ne.g+dis[ne.to];
			T.push(ne);
		}
	}
}
int main(){
//    freopen("1.in","r",stdin);
    freopen("dota.in","r",stdin);
    freopen("dota.out","w",stdout);
	init();
	SPFA();
	/*for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	cout<<endl;*/
	if(p==1)printf("%d\n",A_star(1,n,2));
	else printf("%d\n",dis[1]);
//	while(1);
	fclose(stdin);
    fclose(stdout);
}